Solved

Binomial Que

Posted on 2004-03-24
7
383 Views
Last Modified: 2012-06-21
I have been given code for the array version of a binomial queue. The task is to rewrite the Binomial Queue so that it
is dynamic. The hint is to make it a linked list enabling the queue to increase or grow. While I understand what happens in the array version of the Binomial Queue, I am not sure how the linked list differs from a binary tree.
I have made an attempt but don't think this is correct. I will enclose both code samples. The first code is what I have been given, the array implementation and the second is my solution(the part that needs help).

I gave a high amount of points for the difficulty as I have several days to work on this. Thanks

 
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define QSIZE 50

struct BinQ
{
      int data;
      struct BinQ *child, *sib;
};

typedef struct BinQ BQ;

int Full(BQ **q)
{
      int x, retval=1;

      for(x=0; x<QSIZE && retval; x++)
            if(!q[x])
                  retval = 0;
      return retval;
}

int Empty(BQ **q)
{
      int x, retval=1;

      for(x=0; x<QSIZE && retval; x++)
            if(q[x])
                  retval = 0;

      return retval;
}

void Init(BQ **q)
{
      int x;

      //Set each location in the index array to NULL
      for(x=0;x<QSIZE;x++)
      {
            q[x] = NULL;
      }
}

BQ *NewNode(int data)
{
      BQ *temp;

      if(!(temp = (BQ *)malloc(sizeof(BQ))))
            exit(1);

      temp->data = data;
      temp->child = temp->sib = NULL;

      return temp;
}

//Heart of the algorithm, combine two identical BQ elements
BQ *Combine(BQ *ptr1, BQ *ptr2)
{
      BQ *retval, *temp;

      //retval points to new root, ptr1 points to node to be added
      if(ptr1->data < ptr2->data)
      {
            retval = ptr1;
            ptr1 = ptr2;
      }
      else
            retval = ptr2;

      //easy case, if one element, merge as root's child
      if(!retval->child)
            retval->child = ptr1;
      else
      {
            //otherwise, add to the end of the root's child sibling list
            for(temp = retval->child;temp->sib; temp=temp->sib);
            temp->sib = ptr1;
      }
      return retval;
}

int Insert(BQ **q, int data)
{
      BQ *temp;
      int x;

      if(Full(q)) return 0;

      temp = NewNode(data);

      //Search thru the array combining elements until an empty spot is found
      for(x=0; q[x]; x++)
      {
            temp = Combine(temp, q[x]);
            q[x] = NULL;
      }
      q[x] = temp;
      return 1;
}

int DeleteMin(BQ **q, int *data)
{
      int min, x, y;
      BQ *delnode, *ptr, *temp;

      if(Empty(q)) return 0;

      //Find the minimum value: O(lg(n)) operation
      for(x=0; !q[x]; x++);
      min = x;

      for(; x<QSIZE; x++)
            if(q[x])
                  if(q[x]->data < q[min]->data)
                        min = x;

      //remove the minimum from the structure
      delnode = q[min];
      q[min] = NULL;
      (*data) = delnode->data;

      if(temp = delnode->child)
      {
            x=0;
            //traverse thru the sibling list, reinserting each into the structure
            while(temp)
            {
                  ptr = temp->sib;
                  temp->sib = NULL;
                  for(y=x; q[y]; y++)
                  {
                        temp = Combine(temp, q[y]);
                        q[y] = NULL;
                  }
                  q[y] = temp;
                  x++;
                  temp = ptr;
            }
      }
      free(delnode);
      return 1;
}

//Quick ugly test for the Binomial Queue
int main()
{
      BQ *q[QSIZE];
      int x;

      srand(time(NULL));

      Init(q);
      for(x=0; x<20; x++)
      {
            Insert(q, rand()%100);
      }

      while(DeleteMin(q, &x))
      {
            printf("%d\t", x);
      }

      return 0;
}

MY VERSION
#include <stdio.h>
#include <stdlib.h>


//dynamically allocated heap
//define structures
struct BinQ
{
                int size;
                int data;
  struct BinQ *child, *sib;
 };
typedef struct BinQ BQ;

struct list
{
   BinQ BQ;
  struct List *next;
}

typedef struct list List;




void init(List *q)
{
  q=NULL;
}

BQ *newNode(int data)
{
  List *temp;
  if (!temp=(List*)malloc(sizeof(List))))
  exit(1);

  temp->BQ->data=data
  temp->BQ->child= NULL;
  temp->BQ->sib=NULL;
  return temp;
}

void Insert(List **head, BQ *q, BQ *newNode)
{
    List *ptr;
    if(!(*head))
    (*head)=newNode;
   else
   {
     if((*head)->q->data > newNode->data)  //if q data is greater than newNode data,
     {                               // insert new node before parent

         for(ptr=head; ptr->next != NULL && ptr->BQ->child !=NULL && ptr->BQ->sib != NULL ; ptr=ptr->next)
         {
           newNode->next = ptr;
           ptr->next=newNode;
         }
      }
      else
        head->next = newNode;
}


void insert(BQ *q, BQ *newNode)
{


     if (!(*q))
      (*q)=newNode;
     else
      if (q->data > newNode->data)
      {
           newNode->child=NULL;
       }

}




0
Comment
Question by:closet
  • 3
  • 2
  • 2
7 Comments
 
LVL 8

Assisted Solution

by:ssnkumar
ssnkumar earned 50 total points
ID: 10674313
>BQ *q[QSIZE];
Because of the above statement, the size of the queue is fixed.
So, this is what you have to change. Change that to:
BQ **q = NULL;

In thr Insert() function, do the memory allocation using realloc() like this:
static LengthOfQ = 0;
LengthOfQ++;
q = (BQ **) realloc(q, LengthOfQ * sizeof(BQ));

Now your queue dynamically grows and can hold any number of nodes (memory is the only limit)!

With the change you are trying to do, you have changed it to become a queueu of queue!

Hope this helps....

-ssnkumar
0
 
LVL 4

Accepted Solution

by:
booki earned 450 total points
ID: 10675394
closet,

The structure (for the most part) already exists to implement the binomial queue using linked lists.  Most of the modifications are in Insert and DeleteMin only..

typedef struct BinQ {
      int degree;
      int data;
      struct BinQ *child, *sib;
} BQ;

/*  These functions deleted.. unnecessary
int Full()
int Empty()
void Init()
*/

BQ *NewNode(int data) {
      ........ no changes to the first part of this function .......
      temp->degree = 0;
      return temp;
}

//Heart of the algorithm, combine two identical BQ elements
BQ *Combine(BQ *ptr1, BQ *ptr2) {
      ........ no changes to the first part of this function .......
      ++retval->degree;
      return retval;
}

void Insert(BQ **q, BQ *s) {
      // add subtree S to binomial queue Q
      BQ *temp, *current,*next, **prevptr;
      int degree = s->degree;
      temp = s;
      current = *q;
      prevptr = q;
      // scan through subtrees in Q looking for one with the same degree as S
      while(current != NULL && current->degree <= degree) {
            next = current->sib;
            if (current->degree == degree) {
                  // Now we can start 'adding' trees
                  current->sib = NULL;
                  temp = Combine(temp,current);
                  ++degree;
            } else {
                  prevptr = &current->sib;
            }
            current = next;
      }
      // insert the subtree into Q
      *prevptr = temp;
      temp->sib = current;
}

int DeleteMin(BQ **q, int *data) {
      int min;
      BQ *delnode, **delnodeptr, *ptr, *prev, *temp;

      // return 0 if Q is empty
      if(*q == NULL) return 0;

      //Find the minimum value: O(lg(n)) operation
      ptr = *q;
      min = ptr->data;
      prev = delnode = ptr;
      delnodeptr = q;
      for (ptr=ptr->sib;ptr;ptr=ptr->sib) {
            if (ptr->data < min) {
                  min = ptr->data;
                  delnode = ptr;
                  delnodeptr = &prev->sib;
            }
            prev = ptr;
      }
      //remove the minimum from the structure
      *delnodeptr      = delnode->sib;
      (*data) = delnode->data;

      temp = delnode->child;
      //traverse thru the sibling list, reinserting each into the structure
      while(temp)
      {
            ptr = temp->sib;
            temp->sib = NULL;
            Insert(q,temp);
            temp = ptr;
      }
      free(delnode);
      return 1;
}

//Quick ugly test for the Binomial Queue
int main() {
      BQ *q;
      int x;

      srand(time(NULL));
      q = NULL;
      for(x=0; x<20; x++) {
            Insert(&q, NewNode(rand()%100));
      }

      while(DeleteMin(&q, &x)) {
            printf("%d\t", x);
      }

      return 0;
}


b.
0
 

Author Comment

by:closet
ID: 10679836
Thank you for the timely assistance. I am working on a presentation for Thursday afternoon so won't be able to refocus on this problem until Thurs. night. I will send my responses, questions when I have had a bit more time to reivew. Thank you for now.
Closet
0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 8

Expert Comment

by:ssnkumar
ID: 10684166
Hi closet,

Did you try out my suggestion? Do post your feedback so that we can work on that to improve your code.

-ssnkumar
0
 

Author Comment

by:closet
ID: 10684294
Actually, I have been distracted by a presentation that took over my life for a couple days. I am done now, and will
reveiw the code starting in the AM when my mind is clear. I appreciate the response and will be working on the problem Friday. I tried to work on it when I got home but I am exhausted tonight. Thanks so much

Closet
0
 

Author Comment

by:closet
ID: 10691565
to ssnkumar:
I am afraid I am getting stuck on realloc. I only know malloc
for instance:

int *p=(int *)malloc(sizeof(int))

what what am I doing here?
q = (BQ **) realloc(q, LengthOfQ * sizeof(BQ));

thanks,
closet




0
 
LVL 4

Expert Comment

by:booki
ID: 10693755
ssnkumar,

>> With the change you are trying to do, you have changed it to become a queueu of queue!

By definition a binomial queue is a priority queue made up of a collection of heap ordered binomial trees, or a 'queue of queue' as you put it.  I believe closet's attempt was on the right track.

Also,

>> In thr Insert() function, do the memory allocation using realloc() like this:
>> static LengthOfQ = 0;
static NumTrees = 0;
>> LengthOfQ++;
if LengthOfQ is a power of 2 then {
    NumTrees++;
    q = (BQ **) realloc(q, NumTrees * sizeof(BQ));
}

Otherwise the array grows unnecessarily fast.  For example after 255 calls to insert, there will only be 7 trees in the queue/'forest' while the array has grown to hold 255 trees.
You will need to do something similar for DeleteMin so that the binomial queue does not simply dynamically grow but also shrinks.


closet,

>> The hint is to make it a linked list enabling the queue to increase or grow.

I don't know how stringent the above 'hint' is to your solution but while ssnkumar's approach will definitely make the initial implementation of a binomial queue dynamic, it remains an extension of the initial array approach.

The code i posted is a linked list implementation.

Both are valid and as always there is a time/space tradeoff between the two.. the array approach *may* be slightly faster but the linked list approach will be more memory efficient.

b.
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now