Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Binomial Que

Posted on 2004-03-24
7
Medium Priority
?
393 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
7 Comments
 
LVL 8

Assisted Solution

by:ssnkumar
ssnkumar earned 200 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 1800 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

636 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