Content deleted Content added
Put categories/language links at the bottom |
Correct "sift-down" typo |
||
Line 79:
However, a more common approach is to store the heap in an array. Any binary tree can be stored in an array, but because a heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, for each index ''i'', element ''a''[''i''] is the parent of two children ''a''[2''i''+1] and ''a''[2''i''+2], as shown in the figure. This approach is particularly useful in the [[heapsort]] algorithm, where it allows the space in the input array to be reused to store the heap.
The upheap/downheap operations can be stated then in terms of an array as follows: suppose that the heap property holds for the indices ''b'', ''b''+1, ..., ''e''. The
Only index ''i'' = ''b''-1 can violate the heap property.
Let ''j'' be the index of the largest child of ''a''[''i''] within the range ''b'', ..., ''e''.
| |||