Exercise 3: Sort Using a Heap 📊

Your Task

Write a function heap_sort(nums) that sorts a list in ascending order using only heap operations.

Rules:

✅ Use heapq
❌ Do NOT use .sort() or sorted()

Examples

print(heap_sort([5, 3, 8, 1, 4, 2, 7]))
# Output: [1, 2, 3, 4, 5, 7, 8]

print(heap_sort([10, 1, 10, 1]))
# Output: [1, 1, 10, 10]

print(heap_sort([42]))
# Output: [42]

Hints

💡 Hint 1

A min-heap always pops the smallest element. If you keep popping until it's empty, what order do the elements come out in?

💡 Hint 2 — Step by step

Copy the list (so you don't destroy the original)
heapq.heapify() the copy — this is O(n)
Pop all elements one by one into a result list
Return the result

✅ Solution

import heapq

def heap_sort(nums):
    heap = nums[:]
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

Why this works: heapify arranges the list so the smallest is at the front. Each heappop removes the smallest remaining element, so you get everything in sorted order!

Time: O(n log n) — same as regular sort, but now you understand why it works! 🧠

Bonus Challenge 🌟

Sort in descending order using a heap. (Hint: negate trick!)

print(heap_sort_desc([5, 3, 8, 1, 4]))
# Output: [8, 5, 4, 3, 1]

Sort Using a Heap

Exercise 3: Sort Using a Heap 📊

Your Task

Examples

Hints

Bonus Challenge 🌟

Try it yourself

Code: Sort Using a Heap