krahets/hello-algo · error · IndexError

Heap is empty

Error message

Heap is empty

What it means

MaxHeap.pop raises IndexError('Heap is empty') when is_empty() is true, i.e. the internal max_heap list contains only the reserved logic and no real elements. The guard precedes the swap-and-sift sequence that would otherwise dereference an empty backing store. It encodes the invariant that you cannot extract a maximum from a heap with zero elements. The explicit check gives a clear message instead of an opaque IndexError from list.pop().

Source

Thrown at en/codes/python/chapter_heap/my_heap.py:77

    def sift_up(self, i: int):
        """Starting from node i, heapify from bottom to top"""
        while True:
            # Get parent node of node i
            p = self.parent(i)
            # When "crossing root node" or "node needs no repair", end heapify
            if p < 0 or self.max_heap[i] <= self.max_heap[p]:
                break
            # Swap two nodes
            self.swap(i, p)
            # Loop upward heapify
            i = p

    def pop(self) -> int:
        """Element exits heap"""
        # Handle empty case
        if self.is_empty():
            raise IndexError("Heap is empty")
        # Swap root node with rightmost leaf node (swap first element with last element)
        self.swap(0, self.size() - 1)
        # Delete node
        val = self.max_heap.pop()
        # Heapify from top to bottom
        self.sift_down(0)
        # Return top element
        return val

    def sift_down(self, i: int):
        """Starting from node i, heapify from top to bottom"""
        while True:
            # Find node with largest value among i, l, r, denoted as ma
            l, r, ma = self.left(i), self.right(i), i
            if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
                ma = l
            if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
                ma = r

View on GitHub (pinned to 69932aed18)

Solutions

1. Guard the loop with the provided predicate: `while not heap.is_empty(): x = heap.pop()`.
2. Check emptiness before a single pop: `if not heap.is_empty(): val = heap.pop()`.
3. Use heap.size() to bound a counted extraction loop.
4. In try/except form, catch IndexError specifically and break, reserving it for flow control only when a precondition check is impractical.

Example fix

// before
while True:
    val = heap.pop()  # raises on last iteration
// after
while not heap.is_empty():
    val = heap.pop()

if not heap.is_empty():
    val = heap.pop()

def heap_nonempty(h) -> bool:
    return not h.is_empty()

try:
    val = heap.pop()
except IndexError:
    # heap drained; break the extraction loop
    break

When it happens

Trigger: Calling heap.pop() on a freshly constructed empty heap; calling pop() more times than elements were pushed; draining the heap in a while-true loop without an emptiness exit; popping after a prior pop already returned the last element.

Common situations: Dijkstra/top-K style loops that pop until empty but forget the guard; draining loops `while True: x = heap.pop()`; reusing a heap object across phases without resetting state awareness; off-by-one in batch extraction counts.

Related errors

• Double-ended queue is empty
• Queue is empty
• Stack is empty
• Double-ended queue is empty
• Queue is empty

AI-assisted analysis of krahets/hello-algo@69932aed18 (2026-08-13). Data as JSON: /api/errors/42569241c7dfbfb7. Report an issue: GitHub.