• Status: Solved
• Priority: Medium
• Security: Public
• Views: 406

# Binomial Que

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;
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
}

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

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

}

0
closet
• 3
• 2
• 2
2 Solutions

Commented:
>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

Commented:
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 Commented:
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

Commented:
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 Commented:
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 Commented:
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

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.