heapq

heapq

What it is

heapq is a standard-library module implementing a binary min-heap directly on top of a regular Python list — there’s no separate heap class, just functions (heappush, heappop, etc.) that maintain the heap-ordering invariant on a list you pass in. The smallest element is always at index 0, and heappop removes/returns it in O(log n).

Before this feature

Repeatedly finding and removing the smallest item from a plain list means re-sorting or re-scanning every time:

tasks = [(5, "low priority"), (1, "urgent"), (3, "medium")]

# To get the smallest each time without heapq:
tasks.sort()             # O(n log n) every time something changes
smallest = tasks.pop(0)   # O(n) — pop(0) has to shift every remaining element

After this feature

import heapq

tasks = [(5, "low priority"), (1, "urgent"), (3, "medium")]
heapq.heapify(tasks)              # O(n) -- rearrange in place into heap order

heapq.heappush(tasks, (2, "high priority"))
print(heapq.heappop(tasks))        # (1, 'urgent') -- always the smallest, O(log n)
print(heapq.heappop(tasks))        # (2, 'high priority')

# Common use: "top N" without sorting the whole list
scores = [45, 89, 12, 67, 93, 21, 78]
print(heapq.nlargest(3, scores))    # [93, 89, 78]
print(heapq.nsmallest(3, scores))   # [12, 21, 45]

Why this is better

• Fast repeated min-extraction: heappop is O(log n), versus O(n log n) to re-sort or O(n) to scan for the minimum every time — matters when you’re repeatedly pulling the smallest item as the collection changes (a priority queue is the classic use case).
• In-place on a plain list: no special data structure to import and manage separately — heapq operates directly on a list you already have.
• nlargest/nsmallest avoid a full sort: getting the top 3 out of a million items doesn’t require sorting all million.

Key notes / edge cases

• heapq is a min-heap only — the smallest item is always first. For a max-heap, negate the values on the way in and out (heapq.heappush(h, -value)), or store (-priority, item) tuples as shown above with priorities.
• The heap only guarantees heap[0] is the smallest — the rest of the list is not fully sorted, just heap-ordered (each parent ≤ its children). Don’t assume heap[1] is the second-smallest.
• Ties between equal first elements in tuples fall through to comparing the second element — (1, "urgent") vs (1, "also urgent") would compare the strings, which can raise a TypeError if the second elements aren’t comparable (a common gotcha when heap items are (priority, non-comparable-object)).
• heapify() rearranges an existing list in O(n); pushing items one at a time with repeated heappush costs O(n log n) — prefer heapify() when you already have all the initial items.

Quick practice

1. What’s the time complexity of heapq.heappop()?

   Answer

   O(log n).

2. Does heapq implement a min-heap or a max-heap by default?

   Answer

   A min-heap — `heap[0]` is always the smallest element. A max-heap requires negating values yourself.

3. After calling heapq.heapify(some_list), is the entire list fully sorted?

   Answer

   No — only the heap-order invariant is guaranteed (each parent ≤ its children, so index 0 is the smallest); the rest of the list is not in sorted order.