Heap sort

Heap sort is a sorting algorithm that uses a binary heap data structure. Similar to Insertion sort is can sort-in-place, without extra space requirements.

Binary heap

While the underlaying data is often kept in an array, it’s layout is arranged so this represents a complete binary tree. This may be ordered as either a max heap (parent ≥ child) or min heap (parent ≤ child nodes).

In the case of a max heap indexing is arranged such that for some element at index \(i\) related nodes may be found at the following 1-based indices:

• parent: \(\left\lfloor \frac{i}{2} \right\rfloor\)
• left child: \(2 \times i\)
• right child: \(2 \times i + 1\)

To order the data, a recursive procedure is used.

HEAPIFY(A, i):
    left  ← 2×i
    right ← 2×i + 1
    max   ← i

    n ← length of A

    IF left ≤ n AND A[left] > A[max] THEN
        max ← left

    IF right ≤ n AND A[right] > A[max] THEN
        max ← right

    IF max ≠ i THEN
        swap A[i] and A[max]
        HEAPIFY(A, max)

Algorithm

1. Build a max heap array \(A\) from an unordered array.
2. Swap the first element, which will be the maximum, with the last element \(n\).
3. Decrement \(n\).
4. Run heapify to restore the restore the max-heap property for the remaining data.
5. Return to step 2.

Performance