Binary heap: Difference between revisions

Revision as of 13:40, 29 June 2005

Revision as of 17:36, 15 July 2005

Line 75:

[[Image:Binary_tree_in_array.png|right|A small complete binary tree stored in an array]]

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 aan almost 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 sift-down function extends the heap property to ''b''-1, ''b'', ''b''+1, ..., ''e''.