Heaps

1. When to reach for a heap

You want the largest or smallest thing, over and over, while new things keep arriving.

The alternatives and what they cost:

• Unsorted list. Add is O(1). Finding the max is O(n) every time.
• Sorted list. Finding the max is O(1). Inserting is O(n), because everything shifts.
• Heap. Add is O(log n), reading the extreme is O(1), removing it is O(log n).

The heap wins when you’re doing both operations repeatedly. It loses to a sorted list if you almost never insert, and to an unsorted list if you almost never query.

2. What a heap is

A plain Python list, plus one rule: lst[0] is the smallest element. That’s the entire guarantee.

It is not sorted. Position 5 versus position 6 means nothing. The only promise is about index 0.

The tree people draw is implied by arithmetic, not stored: the children of index i live at 2i+1 and 2i+2. That’s why push and pop are O(log n), it’s the depth of a binary tree over n elements, and why there are no node objects to hold a reference to.

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 3)
heapq.heappush(h, 8)

h[0]                  # 3, O(1), doesn't modify
heapq.heappop(h)      # 3, O(log n), removes it
heapq.heapify(lst)    # O(n), turns an existing list into a heap in place

2.1 heapify vs pushing one at a time

Both produce the same heap from the same data. They cost differently:

• n pushes, each O(log n) → O(n log n)
• heapify → O(n)

The difference is which direction the work goes. heappush sifts a new element up from the bottom, and the bottom is where most of the elements are, so most pushes travel close to the full depth. heapify goes bottom-up sifting elements down, and the bottom half of the array is already valid one-element heaps with nothing to do. Only the few elements near the top have far to travel.

Batch at the start → heapify. Arriving over time → heappush. If items stream in one at a time you have no choice, which is the leaderboard case below.

scores = [50, 30, 70, 10]
heapq.heapify(scores)      # in place

It mutates in place and returns None, so h = heapq.heapify(lst) leaves h as None.

3. Max-heaps

heapq is min-only. For a max-heap, push the negation and negate again on the way out.

heapq.heappush(h, -score)
largest = -heapq.heappop(h)

4. Pushing tuples

Pushing tuples is how you carry extra data alongside the sort key. The heap compares element 0 first, then element 1 as a tiebreak, and so on.

So the sort key has to come first:

heapq.heappush(h, (-score, player))    # orders by score
heapq.heappush(h, (player, -score))    # orders by player name — wrong

5. Top-k

There’s no operation for “give me the k largest.” You pop k times, which is O(k log n), and popping removes them. If the structure has to survive the call, push them back:

def top(self, k):
    taken = []
    while len(taken) < k and self.heap:
        taken.append(heapq.heappop(self.heap))
    for entry in taken:
        heapq.heappush(self.heap, entry)
    return [-score for score, _ in taken]

while ... and self.heap rather than for i in range(k), so asking for more than exists returns what there is instead of raising on an empty pop.

heapq.nlargest(k, iterable) does this in one call and is the right answer when you have a plain iterable rather than a live structure.

6. Lazy deletion

Heaps have no middle-delete. heapq gives you no operation for it, and hand-rolling one means writing your own sift functions and keeping an index map in sync through every swap.

So don’t delete. Mark the entry dead and let whoever reaches it clean up.

The entry stays in the heap doing nothing. When it eventually surfaces at index 0, the operation that was going to look there discards it and looks again.

def remove(self, item):
    self.dead.add(item)          # O(1), heap untouched

def peek(self):
    while self.heap and self.heap[0] in self.dead:
        heapq.heappop(self.heap)
    return self.heap[0] if self.heap else None

Cost. Removal is O(1). A single peek can be O(k log n) if k dead entries have piled up at the top. Amortized it’s O(log n) per element, because every element is pushed once and popped at most once, so total cleanup work across the whole run is bounded by the number of insertions.

Saying that distinction out loud is the point: worst case per call, amortized per element.

What you’re paying. The heap holds garbage, so memory grows with everything ever inserted rather than with what’s live.

The discard has to happen inside the loop, not after it. Popping k entries and then filtering out the dead ones returns fewer than k. You need to keep popping until you have collected k live ones.

6.1 Marking dead when items come back

A set of dead items breaks if the same item can be re-added:

add("a", 50)     push (-50, "a")
remove("a")      "a" is dead
add("a", 60)     "a" is alive again — and the old 50 is too

Fix: a generation counter per item. Removal bumps the generation, and every pushed entry carries the generation it was created under. An entry is stale if its generation is behind the item’s current one.

def __init__(self):
    self.heap = []
    self.generations = defaultdict(int)

def add(self, item, score):
    heapq.heappush(self.heap, (-score, item, self.generations[item]))

def remove(self, item):
    self.generations[item] += 1

def is_live(self, entry):
    _, item, gen = entry
    return gen == self.generations[item]

7. Worked example: a leaderboard with resets

add_score(player, score) records a score. top(k) returns the k highest. reset(player) removes all of that player’s scores.

Resetting by scanning and rebuilding is O(n). Lazy deletion with generations makes it O(1).

import heapq
from collections import defaultdict

class Leaderboard:
    def __init__(self):
        self.scores = []
        self.generations = defaultdict(int)

    def add_score(self, player, score):
        heapq.heappush(self.scores, (-score, player, self.generations[player]))

    def reset(self, player):
        self.generations[player] += 1

    def top(self, k):
        taken = []
        while len(taken) < k and self.scores:
            score, player, generation = heapq.heappop(self.scores)
            if generation == self.generations[player]:
                taken.append((score, player, generation))
        for entry in taken:
            heapq.heappush(self.scores, entry)
        return [-score for score, _, _ in taken]

Stale entries are dropped permanently during the pop loop and never pushed back. Live ones are restored.

8. Mistakes

• Tuple ordered (player, -score), so the heap sorted alphabetically and returned the wrong player’s score. The sort key goes first.
• Popped exactly k and filtered afterwards. With stale entries in the heap that returns fewer than k, and entries deeper down never get a chance. Collect k live ones inside the loop instead.
• Guarded top with an O(n) scan counting live entries. Correct, and it threw away the reason for using a heap. while len(taken) < k and self.heap does the same job for free.
• Said heapify was O(n log n). It’s O(n).