closet
asked on
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(sizeo f(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;
}
}
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(sizeo
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;
}
}
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi closet,
Did you try out my suggestion? Do post your feedback so that we can work on that to improve your code.
-ssnkumar
Did you try out my suggestion? Do post your feedback so that we can work on that to improve your code.
-ssnkumar
ASKER
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
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
ASKER
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
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
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.
>> 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.
ASKER
Closet