Build heap and sort
- Algorithms course
- Intermediate
- Lesson 11/80
- 4 min
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.
Practice 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).
Starter code
def heap_sort(arr):
# Build heap and sortSample 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)Expected output
[1, 2, 5, 8, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Build heap and sort: match the terms
| Term | Meaning |
|---|---|
Build heap |
O(n) |
Sorting |
O(n log n) |
Memory |
O(1) extra |
Stable |
No |
2 How much work does build heap do?
- O(1)
- O(n^2)
- O(log n)
- O(n) Correct answer
Explanation: O(n)
3 Swap target
arr[0], arr[i] = arr[i], ____arr[0], arr[i] = arr[i], arr[0]Explanation: arr[0] is right.