Heap / Priority Queue Field Notes

0Why heaps exist

A normal queue is FIFO: first in, first out. A priority queue removes items by priority instead: the item with the highest priority comes out first, no matter when it was inserted. A heap is the data structure that implements a priority queue, and the two words are often used as if they mean the same thing. It is a special tree-based structure, and its trick is that it can give you the minimum (or maximum) in O(1) and add or remove an item in O(log n), without ever fully sorting.

Two types. A min heap keeps the smallest value at the root, so the smallest has the highest priority to be removed. A max heap keeps the largest at the root. The lessons focus on min heaps; a max heap is the same code with the comparisons flipped.

1Heap properties

Two rules a binary tree must satisfy to be a heap

A binary heap is a binary tree with two extra rules. Both must hold at all times.

1. Structure property. The tree is a complete binary tree: every level is completely filled except possibly the lowest level, and the lowest level is filled contiguously from left to right (no gaps).
2. Order property (min heap). Every descendant is greater than or equal to its ancestors. If the root has value y, every node in the left subtree and the right subtree has a value >= y. This is recursive, like the BST property: it holds again at every subtree. In a max heap every node in the subtrees is <= y.

Unlike a BST, a heap may contain duplicate values. The lesson heap below has 19 twice.

Implementation: arrays under the hood

Heaps are drawn as trees but stored as arrays. No node objects, no left or right pointers. The lesson's example heap is the tree below: root 14; children 19 and 16; 19's children 21 and 26; 16's children 19 and 68; 21's children 65 and 30. In NeetCode's drawing the array is [14,19,16,21,26,19,68,65,30,null,null,null,null,null,null], with unused slots shown as null.

How to fill the array: take an array of size n + 1 where n is the number of nodes. Visit the nodes in BFS order (level by level, left to right) and write them one after another, but start at index 1, not index 0.

One-based indexing: the three formulas

Starting at index 1 lets us compute where a node's children and parent live. Because a binary heap is a complete tree, the array has no gaps, so no pointers are needed. For a node at index i:

leftChild  = 2 * i
rightChild = 2 * i + 1
parent     = i // 2        # integer division

# example: node 19 sits at index 2
#   left child  = 4  → 21
#   right child = 5  → 26
#   parent      = 1  → 14

These formulas only work when the tree is complete and the array is filled contiguously from left to right. That is exactly why the structure property exists.

class Heap:
    def __init__(self):
        self.heap = [0]      # index 0 holds a dummy value; real data starts at index 1

2Push and pop

Reading the min (or max) is O(1): return self.heap[1]. Push and pop are more work, because they must keep both properties true, but each is still O(log n). Both use the same idea: put the value in the only place the structure property allows, then swap it up or down until the order property is true again. That swapping is called percolating (or bubbling).

Push: append, then percolate up

Same heap as before; push 17. The structure property says a complete tree is filled contiguously, so 17 must go at index 10 (the next free slot, which is the left child of 26 at index 5). That may break the order property, because 17 is smaller than 26. Fix it by percolating 17 up until its parent is smaller:

1. Compare 17 with its parent 26 (index 5). Since 17 < 26, swap.
2. Compare 17 with its new parent 19 (index 2). 17 < 19, swap.
3. Compare 17 with its new parent 14 (index 1). 17 > 14, stop.

def push(self, val):
    self.heap.append(val)
    i = len(self.heap) - 1

    # Percolate up
    while i > 1 and self.heap[i] < self.heap[i // 2]:
        tmp = self.heap[i]
        self.heap[i] = self.heap[i // 2]
        self.heap[i // 2] = tmp
        i = i // 2

// is floor division: it rounds down (5.5 becomes 5), which we need because indices must be whole numbers. The loop condition i > 1 stops at the root, which has no parent. The three-line tmp swap is NeetCode's version; in Python you can write it as self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]. For a max heap, flip the comparison to >.

Pop: the obvious way is wrong

Pop removes the highest-priority value, which is the root. The tempting way: remove the root, pull up the smaller child to fill the gap, then fill that gap with the smaller of its children, and so on. The order property stays fine. But look at the structure: after popping 14 and pulling up 16, then pulling 19 up to replace 16, node 19 at index 3 is missing its left child. The tree is no longer complete, the array has a hole, and every index formula breaks.

Pop: the right way

1. Read the root element. That is the value to return.
2. Take the right-most node of the last level (the last array element) and move it into the root. Now the structure property is maintained, because you removed a node from the only place a complete tree can lose one. The order property is violated instead.
3. Percolate the new root down: swap it with min(left_child, right_child) again and again, until both children are >= it or it has no children. Here: 30 goes to the root, swaps with 16, then swaps with 19.

def pop(self):
    if len(self.heap) == 1:
        return None
    if len(self.heap) == 2:
        return self.heap.pop()

    res = self.heap[1]
    # Move last value to root
    self.heap[1] = self.heap.pop()
    i = 1
    # Percolate down
    while 2 * i < len(self.heap):
        if (2 * i + 1 < len(self.heap) and
            self.heap[2 * i + 1] < self.heap[2 * i] and
            self.heap[i] > self.heap[2 * i + 1]):
            # Swap right child
            tmp = self.heap[i]
            self.heap[i] = self.heap[2 * i + 1]
            self.heap[2 * i + 1] = tmp
            i = 2 * i + 1
        elif self.heap[i] > self.heap[2 * i]:
            # Swap left child
            tmp = self.heap[i]
            self.heap[i] = self.heap[2 * i]
            self.heap[2 * i] = tmp
            i = 2 * i
        else:
            break
    return res

Walking through pop() line by line

• Heap is empty (length 1, only the dummy): return None.
• One node (length 2): self.heap.pop() removes and returns it. No adjustment needed.
• Otherwise store the root in res, then move the last value into the root with self.heap[1] = self.heap.pop(). Python's list.pop() with no argument removes the last element and returns it, which is exactly "take the right-most node of the last level".
• The while loop runs as long as a left child exists: 2 * i < len(self.heap). There are three cases for a node: no children, only a left child, two children. A heap can never have only a right child, because that would not be complete.
• Inside the loop a left child is guaranteed. So first check whether a right child exists (2 * i + 1 in bounds), whether it is smaller than the left child, AND whether it is smaller than the current node. If all three: swap with the right child.
• Else, if the current node is greater than its left child: swap with the left child. (This also handles the case where the right child exists but the left one is smaller or equal.)
• Else the node is already in the right position: break.

Push and pop are O(log n) because a complete tree is always balanced: its height is about log n, and each percolation moves at most one level per swap.

3Heapify: build a heap in O(n)

Building a BST with n elements costs O(n log n): n insertions, each O(log n). Building a heap by pushing the elements one at a time also costs O(n log n). But there is a faster way. Heapify takes any array and turns it into a valid heap in O(n).

The idea

The structure property is free: an array with no gaps is a complete tree. Only the order property (parent <= children) needs work. We get it by percolating each element down until it is in the correct position, exactly like the second half of pop(). Leaf nodes cannot move lower, so we skip the whole last level and start from the last non-leaf node, working backwards to the root.

def heapify(self, arr):
    # 0-th position is moved to the end
    arr.append(arr[0])

    self.heap = arr
    cur = (len(self.heap) - 1) // 2
    while cur > 0:
        # Percolate down
        i = cur
        while 2 * i < len(self.heap):
            if (2 * i + 1 < len(self.heap) and
                self.heap[2 * i + 1] < self.heap[2 * i] and
                self.heap[i] > self.heap[2 * i + 1]):
                # Swap right child
                tmp = self.heap[i]
                self.heap[i] = self.heap[2 * i + 1]
                self.heap[2 * i + 1] = tmp
                i = 2 * i + 1
            elif self.heap[i] > self.heap[2 * i]:
                # Swap left child
                tmp = self.heap[i]
                self.heap[i] = self.heap[2 * i]
                self.heap[2 * i] = tmp
                i = 2 * i
            else:
                break
        cur -= 1

1. Move the element at index 0 to the end, so index 0 becomes the dummy slot and the real data starts at index 1. (The old value is still sitting at index 0, but nothing ever reads it.)
2. Compute the index of the first non-leaf node: n // 2, where n is the number of elements. In the code that is (len(self.heap) - 1) // 2.
3. Starting from that node, percolate down exactly as in pop().
4. Decrement the index by 1 and repeat for the next non-leaf node, until the root is done.

Take the unsorted array [68, 30, 65, 21, 19, 14, 26, 16, 19]. After step 1 the heap array is [68, 30, 65, 21, 19, 14, 26, 16, 19, 68]; the real tree is indices 1 to 9. With n = 9 the first non-leaf is index 4, so indices 5 to 9 are leaves and are skipped. The lesson's own visual does the same: heapify runs on the nodes from index 4 down to 1.

The result is a valid min heap: 14 at the top, and every parent is <= its children. Note that the root did 3 swaps while index 4 did none. That imbalance is the whole reason heapify is O(n).

Why O(n) and not O(n log n)

With n nodes, roughly n/2 are leaves and n/2 are non-leaves. Only the non-leaves percolate down. Nodes on the second-lowest level can percolate at most 1 level. The level above that can percolate at most 2. And so on: the root can percolate all the way down. But the number of nodes halves each level you go up, while the distance they can travel only grows by one. The sum of all that work simplifies to O(n).

4heapq: the heap you actually use in Python

The lesson code is for understanding. In interviews and real code you use the heapq module from the standard library. It is a min heap built on a plain Python list. Three things to know before anything else: it is 0-indexed (no dummy slot), it is a set of functions that operate on your list (not a class), and it only does min heaps directly.

The API

import heapq

heap = []
heapq.heappush(heap, 19)        # O(log n), percolate up
heapq.heappush(heap, 14)
heapq.heappush(heap, 16)
heap[0]                         # → 14   peek at the min, O(1). Do NOT pop to look.
heapq.heappop(heap)             # → 14   O(log n), last-to-root then percolate down

nums = [14, 19, 16, 21, 26, 19, 68, 65, 30]
heapq.heapify(nums)             # O(n), in place, reorders the SAME list
nums[0]                         # → 14

heapq.heappushpop(heap, x)      # push x, then pop the min  (faster than two calls)
heapq.heapreplace(heap, x)      # pop the min, then push x  (heap must be non-empty)

heapq.nlargest(2, [5, 1, 9, 3, 7])            # → [9, 7]
heapq.nsmallest(2, [5, 1, 9, 3, 7])           # → [1, 3]
heapq.nsmallest(1, ["kiwi", "fig", "banana"], key=len)   # → ["fig"]

nlargest and nsmallest return a sorted list of the k extreme items and accept a key= like sorted does. For small k they run in about O(n log k); for k close to n it is cheaper to just sort.

Max heap: negate on the way in, negate on the way out

heapq has no max-heap mode. The standard trick: push -x instead of x. The smallest negative is the largest original, so -heap[0] is the max. Every place you read a value, put the minus sign back.

maxh = []
for v in [3, 10, 7]:
    heapq.heappush(maxh, -v)     # store negatives
-maxh[0]                         # → 10   the max
-heapq.heappop(maxh)             # → 10
-heapq.heappop(maxh)             # → 7

# LeetCode 1046 Last Stone Weight: always smash the two heaviest
def lastStoneWeight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        first = -heapq.heappop(heap)          # heaviest
        second = -heapq.heappop(heap)         # second heaviest
        if first != second:
            heapq.heappush(heap, -(first - second))
    return -heap[0] if heap else 0

lastStoneWeight([2, 7, 4, 1, 8, 1])   # → 1

Tuples: priority first, tie-breaker second, payload last

Python compares tuples element by element, so a heap of tuples is ordered by the first element, then the second, and so on. Put the priority first. If two items can have the same priority, put a tie-breaker (a counter, an index) second, so the comparison never reaches the payload. This matters when the payload is an object that cannot be compared: Python raises TypeError.

tasks = []
heapq.heappush(tasks, (2, 1, "write tests"))    # (priority, insertion order, payload)
heapq.heappush(tasks, (1, 2, "fix bug"))
heapq.heappush(tasks, (1, 0, "answer pager"))
heapq.heappop(tasks)     # → (1, 0, "answer pager")   priority 1, earliest
heapq.heappop(tasks)     # → (1, 2, "fix bug")
heapq.heappop(tasks)     # → (2, 1, "write tests")

# without a tie-breaker, equal priorities compare the payloads:
heapq.heappush(bad, (1, Job("a")))
heapq.heappush(bad, (1, Job("b")))   # TypeError: '<' not supported between Job and Job

5Moves that solve most heap problems

The lessons teach the structure. Interviews test whether you recognize when a heap is the tool. These four moves cover most heap questions.

Move 1: Top-K with a heap of size k

When: "find the k largest / smallest / closest / most frequent". Keep a heap of size k. For the k largest, use a min heap: push every element, and whenever the heap grows past k, pop the smallest. What survives is the k largest, and the root is the k-th largest. Cost O(n log k), which beats sorting when k is small.

def findKthLargest(nums, k):          # LeetCode 215
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)          # throw away the smallest
    return heap[0]                       # k-th largest sits at the root

findKthLargest([3, 2, 1, 5, 6, 4], 2)     # → 5


class KthLargest:                        # LeetCode 703: same idea, but the stream keeps coming
    def __init__(self, k, nums):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]


def kClosest(points, k):                 # LeetCode 973: k SMALLEST → max heap of size k
    heap = []
    for x, y in points:
        d = x * x + y * y
        heapq.heappush(heap, (-d, x, y))     # negate: max heap on distance
        if len(heap) > k:
            heapq.heappop(heap)              # drop the farthest
    return [[x, y] for _, x, y in heap]


def topKFrequent(nums, k):               # LeetCode 347: count, then nlargest by count
    count = Counter(nums)
    return [x for x, _ in heapq.nlargest(k, count.items(), key=lambda p: p[1])]

Move 2: k-way merge

When: "merge k sorted lists / arrays / streams". Put the first element of every list in a heap, tagged with which list it came from. Pop the smallest, then push the next element from that same list. Every element passes through a heap of size at most k, so the total is O(N log k) for N elements. The tuple is (value, list_index, position): the list index is the tie-breaker.

def mergeKSorted(lists):                 # LeetCode 23 on plain lists
    heap = []
    for li, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], li, 0))    # (value, which list, index in it)
    out = []
    while heap:
        val, li, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][j + 1], li, j + 1))
    return out

mergeKSorted([[1, 4, 5], [1, 3, 4], [2, 6]])   # → [1, 1, 2, 3, 4, 4, 5, 6]

For linked lists (the real LeetCode 23) push (node.val, i, node) and advance with node.next; the i keeps two equal values from ever comparing ListNode objects.

Move 3: Two heaps for a running median

When: "median of a stream", or any "split the data into a lower half and an upper half" problem. Keep the lower half in a max heap and the upper half in a min heap. The median is then at one root or the average of both. Two rules after every insert: every element of the lower half must be <= every element of the upper half, and the sizes may differ by at most 1.

class MedianFinder:                      # LeetCode 295
    def __init__(self):
        self.small = []      # max heap (negated): lower half
        self.large = []      # min heap: upper half

    def addNum(self, num):
        heapq.heappush(self.small, -num)
        # rule 1: every element of small must be <= every element of large
        if self.large and -self.small[0] > self.large[0]:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        # rule 2: sizes may differ by at most 1
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small) + 1:
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        if len(self.large) > len(self.small):
            return self.large[0]
        return (-self.small[0] + self.large[0]) / 2

Move 4: Heap or sort? The decision

A heap is not "a faster sort". It is a structure for when the data keeps changing or when you need only a few extremes. Use this table when you feel the urge to call sorted().

Rule of thumb: if the word "stream", "repeatedly", "each time", "k-th", or "top k" appears in the problem, think heap. If it says "sort" and the data does not change, just sort.

6Big-O summary

Say these out loud in interviews. n is the number of elements in the heap; k is the size of a bounded heap.

The heap gives up one thing to get its speed: there is no fast search for a random value, and no fast "delete this specific element". A heap only knows where its min is. If you need arbitrary deletes, the usual trick is lazy deletion: mark the item as dead in a set, and skip dead items when they reach the root.

7Mistakes to watch for

8Practice, in this order

Notes do not make you good at this. Solving does. Do these on LeetCode with no notes open, then check against the templates above.

Your next step today: LeetCode 1046. Write it with heapq and the negation trick from memory, run it, then re-read the max heap block in section 4 and compare.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.