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.

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)
```

- Build a max heap array \(A\) from an unordered array.
- Swap the first element, which will be the maximum, with the last element \(n\).
- Decrement \(n\).
- Run
`heapify`

to restore the restore the max-heap property for the remaining data. - Return to step 2.

Worst | Average | Best | |
---|---|---|---|

Time |
\(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) |

Space |
\(O(n)\) |