Hey guys, I'm having a doubt on min-heaps I thought you could help.
I'm supposed to write a function that tests if a min-heap is well constructed, by other words, if all the sequences of numbers from the root till the last leaf are increasing.
My struct is as following :
Any help ?Code:typedef struct minheap { int values[]; int used; int size; } *MinHeap;
I thought about going from i=0 till i = used but that would only search one one way I think :/
If understood well,you want to check if the children of any parent have bigger values than him.You could use recursion. The root is the parent of the nodes that are the children of the root.Then every children becomes a parent which may have some children.Then these children are the parents for their children and so one
Yeah but I wanna do it for every single way from the root till the left leafs.
How can I do it by recursion and how am I supposed to check his children (I have no way to do so).
For example, my values array might be 1,4,6,9 when the children in the left is 6 and I wanna check that way but doing it recursively I would check 4 first correct ?
It seems to me that it is quite easy to do this iteratively: for each node, check that its immediate children are less than or equal to itself.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
I think i have not understand something.What you want to do in the min-heap 1,4,6,9 is to go down from root like this :
from 1 to 4,from 4 to 9 and then 9 is a leaf
from 1 to 6 and then 6 is a leaf
Okay, recursion is perfect for that. Just stop trying to recurse down farther once you hit a NULL node (or the equivalent in your array-based version).
Do you know what recursion is in general? Can you, for example, write a recursive function to calculate terms of the Fibonacci sequence? Can you implement a basic binary search tree recursively? If not, either use an iterative approach or set the MinHeap aside and practice recursion.How can I do it by recursion and how am I supposed to check his children (I have no way to do so).
You check whatever one you want first. If you want to only check the left child, do so. If only the right, check only the right. If you want to check right first, then left, do that. The choice is up to you.For example, my values array might be 1,4,6,9 when the children in the left is 6 and I wanna check that way but doing it recursively I would check 4 first correct ?
It looks like you're implementing this heap as an array without fully understanding the mechanics of the data structure. First, make sure you can implement a basic binary search tree using pointers and node allocation (i.e. not arrays). Then, figure out how to translate that to an array-based binary search tree.Once you understand that, it should be easy to translate the canonical heap implementation to an array based one.
Last edited by anduril462; 08-28-2012 at 10:09 AM. Reason: removed stray quote tag
Err... the canonical heap implementation is an array based one, for both min-heap and max-heap.
This is why I think that using recursion is very much unnecessary here: it is so simple to loop over the elements of the array and verify that each element and its children satisfy the min-heap property.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
Since a heap is a complete binary tree (except possibly for the lowest elements), it is implemented as an array for efficency.
To make sure we're on the same page, this
1 2 3 4 5 6
represents this:
So, yeah, recursion is pointless for this.Code:. 1 2 3 4 5 6
As for "I have no way to check his children", I'm not sure what you mean by that. Didn't you learn about heaps? The children are easy to find; consider how to implement LEFT_CHILD and RIGHT_CHILD above.Code:int bad_heap = 0; for (i = 0; LEFT_CHILD(i) < size; i++) if (a[i] > a[LEFT_CHILD(i)] || a[i] > a[RIGHT_CHILD(i)]) { // use < for max heap bad_heap = 1; break; }
The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss
Alright guys, thanks for all the replies.
Iteratively it's so easy!
Interesting...I only recall learning the binary tree version.
Agreed, given his array implementation, iteration would be a better solution. My suggestion however was largely driven by the fact that he was visualizing the heap in a binary tree format, but couldn't figure out how to manipulate or access any of the elements in his array implementation. I think using a model that more closely matches what's in his head to figure out what to do first, then mapping/translating that to the array implementation would be beneficial. It's two smaller mental leaps rather than one large one.This is why I think that using recursion is very much unnecessary here: it is so simple to loop over the elements of the array and verify that each element and its children satisfy the min-heap property.
EDIT: Moot point I guess, he's got his answer
Last edited by anduril462; 08-28-2012 at 10:11 AM.
