Database Reference
In-Depth Information
Figure A1-17.
Heap Construction Algorithm
Example 9:
Figure
A1-18
shows how a maximum heap is constructed with the
following nodes:6 25 7 2 14 10 9 22 3 16.
Figure A1-18.
Illustration of Heap Construction
A1.6.2 Processing the Heap (Heap Sort)
The algorithm for processing the heap (also called heap-sort because it produces a sorted
list) is shown in Figure
A1-19
. The algorithm shown assumes a max-heap; it progressively
removes the root of the heap until it is empty. Heap-sort performs as well as quick-sort on
the average and better than quick-sort at worst; it is an O(N Log N) algorithm.
1
2
3
4
Figure A1-19.
Heap-sort Algorithm
