home

# 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.
Time $$O(n \log n)$$ $$O(n \log n)$$ $$O(n)$$
Space $$O(n)$$