Solved

# Binomial Que

Posted on 2004-03-24

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;

}

}