Implementation of heaps

A heap is a list with the following attributes:
Each entry contains a key.
For all positions k in the list, the key at position k is least as large as the keys in positions 2k and 2k+1, provided these positions exist in the list. Therefore, an array can be used to implement a heap as shown in following figure.

A heap is definitely not an ordered list because the first entry in the heap has the largest key, and there is no necessary ordering between the keys in locations k and k+1, if k > 1.
A heap is used in sorting a continuous list of length n in O(n log2(n)) comparisons and movements of entries, even in the worst case. The corresponding sorting method is called heapsort.


You may also like...