Build heap and sort

Build a heap, then extract one by one to sort.

Build heap and sort

Heap sort runs in two phases. First, we turn the array into a max-heap: for every i from the last non-leaf to the root, call heapify(arr, n, i). This is O(n).

Then the root (largest) is swapped with the last element, the heap shrinks by one, and heapify is called on the root. This repeats n-1 times; each is O(log n).

Total: O(n log n). In-place, not stable.

Move root to end

Once the max-heap is built, the root arr[0] is the largest. We swap it with arr[n-1]; the largest element is now in place.

Then the heap size drops to n-1 and the root is heapified. This brings the second largest to the top. Repeat.

Each swap + heapify places one element. After n steps the array is sorted.

Exercise Heap sort

Write heap_sort(arr). Build a max-heap, then move root to end and heapify. Print [1, 2, 5, 8, 9] with arr=[5,2,8,1,9]; heap_sort(arr); print(arr).

Show example solution

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    # Build heap and sort
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
arr = [5, 2, 8, 1, 9]
heap_sort(arr)
print(arr)

Test yourself

Build heap and sort: match the terms

Build heap

O(n)
Sorting

O(n log n)
Memory

O(1) extra
Stable

No
How much work does build heap do?
- O(1)
- O(n^2)
- O(log n)
- O(n)
Show answer

O(n) — O(n)

Swap target

arr[0], arr[i] = arr[i], ____

Show answer

arr[0], arr[i] = arr[i], arr[0]

Next lesson: Summary - Heap sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies