Editing Heapsort (section)

== Overview ==
The heapsort algorithm can be divided into two phases: heap construction, and heap extraction.

The heap is an [[implicit data structure]] which takes no space beyond the array of objects to be sorted; the array is interpreted as a [[complete binary tree#Types of binary trees|complete binary tree]] where each array element is a node and each node's parent and child links are defined by simple arithmetic on the array indexes. For a zero-based array, the root node is stored at index 0, and the nodes linked to node {{code|i}} are <pre>
  iLeftChild(i)  = 2⋅i + 1
  iRightChild(i) = 2⋅i + 2
  iParent(i)     = floor((i−1) / 2)
</pre> where the [[floor function]] rounds down to the preceding integer.  For a more detailed explanation, see {{section link|Binary heap|Heap implementation}}.

This binary tree is a max-heap when each node is greater than or equal to both of its children.  Equivalently, each node is less than or equal to its parent.  This rule, applied throughout the tree, results in the maximum node being located at the root of the tree.

In the first phase, a heap is built out of the data (see {{section link|Binary heap|Building a heap}}).

In the second phase, the heap is converted to a sorted array by repeatedly removing the largest element from the heap (the root of the heap), and placing it at the end of the array. The heap is updated after each removal to maintain the heap property. Once all objects have been removed from the heap, the result is a sorted array.

Heapsort is normally performed in place. During the first phase, the array is divided into an unsorted prefix and a heap-ordered suffix (initially empty).  Each step shrinks the prefix and expands the suffix.  When the prefix is empty, this phase is complete.  During the second phase, the array is divided into a heap-ordered prefix and a sorted suffix (initially empty).  Each step shrinks the prefix and expands the suffix.  When the prefix is empty, the array is sorted.