Min-heap

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 :

Code:

---

typedef struct minheap {
int values[];
int used;
int size;
} *MinHeap;

---

Any help ?

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.

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

Quote:

---

Originally Posted by DeanWinchester

Yeah but I wanna do it for every single way from the root till the left leafs.

---

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).

Quote:

---

How can I do it by recursion and how am I supposed to check his children (I have no way to do so).

---

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.

Quote:

---

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 ?

---

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.

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.

Quote:

---

Originally Posted by anduril462

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.

---

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.

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:

Code:

---

.      1
    2    3
  4 5  6

---

So, yeah, recursion is pointless for this.

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

---

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.

Alright guys, thanks for all the replies.
Iteratively it's so easy!

Quote:

---

Originally Posted by laserlight

Err... the canonical heap implementation is an array based one, for both min-heap and max-heap.

---

Interesting...I only recall learning the binary tree version.

Quote:

---

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.

---

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.

EDIT: Moot point I guess, he's got his answer