Summary - Heap sort
- Algorithms course
- Intermediate
- Lesson 12/80
- 4 min
Implement heap sort and print the result.
Summary - Heap sort
Heap sort: build heap (O(n)) + n-1 swap/heapify (O(n log n)). In-place, O(1) extra memory. Not stable.
Even in the worst case it gives O(n log n); this is an advantage over quick sort. But the constant factor is usually higher.
The heap data structure is used on its own in priority queue applications.
Practice Summary: heap sort
Write heap_sort(arr). Print [1, 1, 2, 3, 4, 5, 9] with arr=[3,1,4,1,5,9,2]; 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 = [3, 1, 4, 1, 5, 9, 2]
heap_sort(arr)
print(arr)Expected output
[1, 1, 2, 3, 4, 5, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Heap sort: match the terms
| Term | Meaning |
|---|---|
Build heap |
O(n) |
Sorting |
O(n log n) |
Memory |
O(1) extra |
Stable |
No |
2 Root index
Question
arr[____]
Answer
arr[0]Explanation: 0 is right.
3 What is the memory cost of heap sort?
- O(1) extra Correct answer
- O(log n)
- O(n^2)
- O(n)
Explanation: O(1) extra