I need to determine if the array is a valid min heap. And if it is not, which values are out of place? I am confused about heaps already, so this is difficult for me. Can anyone explain it to me, please?
[0, 6, 2, 26, 24, 22, 20, 48, 46, 44]
Asked
Active
Viewed 1,027 times
3 Answers
1
In an array based min heap the items are stored in a full binary tree. Assuming a 0-based array, this means that the left child of the item in index i would be in index 2i + 1 and the right child will be in index 2i + 2.
The min heap invariant is that each node is smaller than its descendants. Therefore, in order to check whether the heap is a legal one all you need to do is to go through all the internal nodes and make sure that this condition holds, i.e. for each internal heap node in index i, a[i] < a[2*i + 1] && a[i] < a[2*i + 2].
Amnon Shochot
- 8,998
- 4
- 24
- 30
0
Here is your heap in a more graphical form if that helps. The invariant is that each parent is less than both its children.
0
6 2
26 24 22 20
48 46 44
As you can see each node is greater than its parent so this is a valid min heap.
Guvante
- 18,775
- 1
- 33
- 64
-
I understand that question now. However, now I have to add and remove from the min heap Initial Configuration: [0, 2, 4, 6, 8, 10, 12, 14] Insert 1 Remove 4 Remove 0 Insert 3 – William Diuguid Apr 07 '15 at 07:01
-
I think the insert 1 would produce [0,1,4,2,8,10,12,14,6] – William Diuguid Apr 07 '15 at 07:04
-
@WilliamDiuguid: Insert means "append to end of array and swap with parent while that parent is greater than self" which matches your example. Remove means "swap root node with last element and swap that element with the smallest of its children until it is a leaf or smaller than its children". Remove 4 would be [0, 1, 6, 2, 8, 10, 12, 14] as the 6 that gets swapped in happens to be in the right spot. – Guvante Apr 07 '15 at 14:38
