|
|
|
|
The Heapsort algorithm uses a special data structure known as a heap. Recall a complete binary tree has the maximum possible number of nodes at every level except possibly the last level in which all of the leaves are as far to the left as possible. Complete binary trees will have one of the following shapes. A heap is a complete binary tree with the partial order property that the value stored in a node is greater than or equal to any of its children.