DeleteMin Data Structure in C
Does anyone have any suggestions on how to make this cleaner? It always leaves the last node.
Thanks,
Dan
int DeleteMin(BQ *head, int *data)
{
BQ *delnode,*temp,*ptr,*ptr1,
if(Empty(head)) return 0;
if(!head->sib->sib && !head->sib->child)
{
free(head->sib);
return 0;
}
for(ptr=head;!ptr->sib->ch
delnode=ptr;
for(ptr->sib; ptr; ptr=ptr->sib)
{
if(ptr->child)
{
if(ptr->child->data<delnod
delnode=ptr;
}
}
ptr1=delnode->child;
delnode->child=NULL;
(*data)=ptr1->data;
if(temp = ptr1->child)
{
while(temp)
{
ptr = temp->sib;
temp->sib = NULL;
Combine(head->sib, temp);
temp = ptr;
head = head->sib;
}
}
free(ptr1);
for(headtemp;headtemp->sib
if(!headtemp->sib->child)
{
free(headtemp->sib);
headtemp->sib=NULL;
}
return 1;
}
Thanks,
Dan
int DeleteMin(BQ *head, int *data)
{
BQ *delnode,*temp,*ptr,*ptr1,
if(Empty(head)) return 0;
if(!head->sib->sib && !head->sib->child)
{
free(head->sib);
return 0;
}
for(ptr=head;!ptr->sib->ch
delnode=ptr;
for(ptr->sib; ptr; ptr=ptr->sib)
{
if(ptr->child)
{
if(ptr->child->data<delnod
delnode=ptr;
}
}
ptr1=delnode->child;
delnode->child=NULL;
(*data)=ptr1->data;
if(temp = ptr1->child)
{
while(temp)
{
ptr = temp->sib;
temp->sib = NULL;
Combine(head->sib, temp);
temp = ptr;
head = head->sib;
}
}
free(ptr1);
for(headtemp;headtemp->sib
if(!headtemp->sib->child)
{
free(headtemp->sib);
headtemp->sib=NULL;
}
return 1;
}
what is BQ data type and what is this function delmin supposed to do ?
ASKER
Sorry,
DeleteMin is supposed to recursively delete nodes of a Binomial Queue until all are gone. The original is an array operation that I am converting to a dynamic. Wish I could post the original code but it's about twice as big as what I've already posted.
Thanks for taking the time to look.
Dan
DeleteMin is supposed to recursively delete nodes of a Binomial Queue until all are gone. The original is an array operation that I am converting to a dynamic. Wish I could post the original code but it's about twice as big as what I've already posted.
Thanks for taking the time to look.
Dan
>Wish I could post the original code but it's about twice as big as what I've already posted.
that would not be a problem ... post it
Also post the definition for BQ
that would not be a problem ... post it
Also post the definition for BQ
Hi Rocky,
Like Sunny, I don't have much experience with Binomial Queues. A google search did find a lot of things to study. :) Here's a pretty good pictoral: http://lcm.csa.iisc.ernet.in/dsa/node141.html. The thing that I don't understand is "child management". I would expect the nodes of a structure named "binomial" to have, at most, 2 children. The pictoral shows quite a few nodes with 3.
Just to see if I understand the concept, each node in the queue (tree) contains the depth of the queue at that node. This implies that nodes are always added to or delete from the top of the structure so that the depth need not be recomputed every time the structure is changed. Merging of structures can occur only when the two structures are the same depth. (An interesting concept.) Intuitively, I would expect that the merge occurs such that the head of both of the structures are peers (at the same level) in the new structure. However, the pictoral suggests differently.
On to the questions.....
It would seem that the DeleteMin() function would only need to delete the head of the structure and adjust the children as required. (The trees all appear to be "right handed" with the head being the smalled element.) If this is so, deletion should be nearly trivial, and restructuring the tree should be "complicated" only when rebalancing the remaining nodes.
1) How many children can a node have? The pictoral often shows three links from the head. How are they "managed"?
2) Why a recursive deletion? The only application for this that I can see is to move the children of the deleted node to another node. If this is the case, I would expect the recursive process to be searching for the appropriate node to insert the abandoned children. That is, search for all nodes with a "depth" of the deleted node and move the children to the most appropriate node.
3) You state that your function always leaves "the last node". Can you explain what you mean by this?
Kent
Like Sunny, I don't have much experience with Binomial Queues. A google search did find a lot of things to study. :) Here's a pretty good pictoral: http://lcm.csa.iisc.ernet.in/dsa/node141.html. The thing that I don't understand is "child management". I would expect the nodes of a structure named "binomial" to have, at most, 2 children. The pictoral shows quite a few nodes with 3.
Just to see if I understand the concept, each node in the queue (tree) contains the depth of the queue at that node. This implies that nodes are always added to or delete from the top of the structure so that the depth need not be recomputed every time the structure is changed. Merging of structures can occur only when the two structures are the same depth. (An interesting concept.) Intuitively, I would expect that the merge occurs such that the head of both of the structures are peers (at the same level) in the new structure. However, the pictoral suggests differently.
On to the questions.....
It would seem that the DeleteMin() function would only need to delete the head of the structure and adjust the children as required. (The trees all appear to be "right handed" with the head being the smalled element.) If this is so, deletion should be nearly trivial, and restructuring the tree should be "complicated" only when rebalancing the remaining nodes.
1) How many children can a node have? The pictoral often shows three links from the head. How are they "managed"?
2) Why a recursive deletion? The only application for this that I can see is to move the children of the deleted node to another node. If this is the case, I would expect the recursive process to be searching for the appropriate node to insert the abandoned children. That is, search for all nodes with a "depth" of the deleted node and move the children to the most appropriate node.
3) You state that your function always leaves "the last node". Can you explain what you mean by this?
Kent
rockybalboa,
This seems to be similar to a recent post. See my post for a sol'n.
https://www.experts-exchange.com/questions/20930975/Binomial-Que.html
b.
This seems to be similar to a recent post. See my post for a sol'n.
https://www.experts-exchange.com/questions/20930975/Binomial-Que.html
b.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I see several things that need cleaning up. If you'll tell me a bit more about what the function is supposed to do I'll be glad to offer some suggestions.
Kent