Exercise 3: Build a Heap from Scratch 🔨

Your Task

Implement a MinHeap class without using Python's heapq module. You need to write the core operations yourself:

1. bubble_up(i) — After inserting at the end, move the element up until the heap property is restored
2. bubble_down(i) — After removing the root, move the replacement element down until the heap property is restored
3. insert(val) — Add a value to the heap
4. extract_min() — Remove and return the smallest value
5. heapify(lst) — Turn an arbitrary list into a valid min-heap

Heap property: Every parent must be ≤ both of its children.

Remember: A heap is stored as a flat list where for index i:

• Parent: (i - 1) // 2
• Left child: 2 * i + 1
• Right child: 2 * i + 2

---

Examples

h = MinHeap()
h.insert(5)
h.insert(3)
h.insert(8)
h.insert(1)
print(h.extract_min())
# Output: 1
print(h.extract_min())
# Output: 3

h2 = MinHeap()
h2.heapify([9, 4, 7, 1, 3])
print(h2.extract_min())
# Output: 1
print(h2.extract_min())
# Output: 3

---

Expected Complexity

Operation	Time	Space
insert	O(log n)	O(1)
extract_min	O(log n)	O(1)
bubble_up	O(log n)	O(1)
bubble_down	O(log n)	O(1)
heapify	O(n)	O(1)

Why is heapify O(n)? Most nodes are near the bottom and barely move. Only the few nodes near the top bubble down far. The math works out to O(n) total, not O(n log n).

---

Starter Code

class MinHeap:
    def __init__(self):
        self.data = []

    def bubble_up(self, i):
        # Your code here
        pass

    def bubble_down(self, i):
        # Your code here
        pass

    def insert(self, val):
        # Your code here
        pass

    def extract_min(self):
        # Your code here
        pass

    def heapify(self, lst):
        # Your code here
        pass

# Test insert + extract_min:
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2, 7]:
    h.insert(v)
print(h.extract_min())
# Output: 1
print(h.extract_min())
# Output: 2
print(h.extract_min())
# Output: 3

# Test heapify:
h2 = MinHeap()
h2.heapify([9, 4, 7, 1, 3])
print(h2.extract_min())
# Output: 1
print(h2.extract_min())
# Output: 3

---

Hints

---

Bonus Challenge 🌟

Implement peek() (return min without removing) and size(), then convert your MinHeap into a MaxHeap by changing the comparison direction in bubble_up and bubble_down.