Data Structures & Algorithms Cheatsheet

Heaps and Priority Queues

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity And Layout

A binary heap is a complete tree stored in an array. Every node is ≤ its children (min-heap), so the extreme is always at index 0.

Operation	Time	Note
peek min or max	O(1)	index 0
push	O(log n)	sift up
pop extreme	O(log n)	swap last to root, sift down
heapify an existing array	O(n)	not O(n log n), the bound is tighter
build by n pushes	O(n log n)	slower, always heapify instead
delete arbitrary element	O(n)	O(log n) with an index map
decrease-key	O(log n)	needs the index, or lazy deletion
search for a value	O(n)	a heap is not searchable
merge two heaps	O(n + m)	O(log n) with a pairing or Fibonacci heap

Space is O(n) with zero pointer overhead, since the tree is implicit in the array indices.

Array Index Arithmetic

For a 0-indexed heap of size n:

Relation	Formula
parent of i	`(i - 1) // 2`
left child of i	`2 * i + 1`
right child of i	`2 * i + 2`
last non-leaf node	`n // 2 - 1`
is i a leaf	`2 * i + 1 >= n`
height	⌊log₂ n⌋

Heapify walks from the last non-leaf down to 0, which is why it is O(n) and not O(n log n): most nodes are near the bottom and sift almost nowhere.

Python heapq

heapq is a min-heap only, operating in place on a plain list.

import heapq

h = [5, 1, 3]
heapq.heapify(h)               # in place, O(n)
heapq.heappush(h, 2)           # O(log n)
smallest = heapq.heappop(h)    # O(log n), IndexError if empty
h[0]                           # peek, O(1)
len(h)

heapq.heappushpop(h, x)        # push then pop, one sift
heapq.heapreplace(h, x)        # pop then push, one sift, h must be non-empty
heapq.nsmallest(3, data)       # O(n log k)
heapq.nlargest(3, data, key=len)
list(heapq.merge(a, b, c))     # lazy merge of sorted iterables, O(total)

Max-heap in Python: negate the values, or negate the sort key.

h = [-x for x in nums]
heapq.heapify(h)
largest = -heapq.heappop(h)

# tuples compare element by element, so pack the priority first
heapq.heappush(h, (-count, word))         # count desc, word asc

# tie-break with a counter when the payload is not comparable
import itertools
tie = itertools.count()
heapq.heappush(h, (priority, next(tie), obj))

Pushing (priority, obj) where two objects share a priority raises TypeError if obj has no <. Insert a monotonic counter as the second element to guarantee a total order.

Java And C++

PriorityQueue<Integer> minHeap = new PriorityQueue<>();     // min by default
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<int[]> byFirst =
    new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

minHeap.offer(5);        // add, O(log n)
minHeap.peek();          // O(1), null if empty
minHeap.poll();          // remove, O(log n), null if empty
minHeap.remove(x);       // O(n) linear scan
new PriorityQueue<>(Arrays.asList(a));   // O(n) heapify
// Iterating a PriorityQueue does NOT give sorted order.

priority_queue<int> maxHeap;                            // MAX-heap by default
priority_queue<int, vector<int>, greater<int>> minHeap; // min-heap
maxHeap.push(5); maxHeap.top(); maxHeap.pop();          // pop returns void

// heap operations on a raw vector
make_heap(v.begin(), v.end());     // O(n), max-heap
push_heap(v.begin(), v.end());     // after v.push_back(x)
pop_heap(v.begin(), v.end());      // moves max to the back, then v.pop_back()
sort_heap(v.begin(), v.end());     // heapsort in place
nth_element(v.begin(), v.begin() + k, v.end());   // O(n) quickselect

Java is min by default, C++ is max by default. That inversion causes more bugs than any other detail on this page.

Top K Patterns

The rule: for the k largest, keep a min-heap of size k. The root is the weakest survivor, so it is the one to evict.

import heapq

def k_largest(nums, k):
    """O(n log k) time, O(k) space. Beats sorting when k << n."""
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)        # drop the smallest survivor
    return h                        # unordered, sort if needed

def kth_largest(nums, k):
    h = nums[:k]
    heapq.heapify(h)
    for x in nums[k:]:
        if x > h[0]:
            heapq.heapreplace(h, x)
    return h[0]

def top_k_frequent(words, k):
    """Count desc, then lexicographic asc among ties."""
    from collections import Counter
    cnt = Counter(words)
    return heapq.nsmallest(k, cnt, key=lambda w: (-cnt[w], w))

def k_closest_to_origin(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

Goal	Heap type	Size	Complexity
k largest	min-heap	k	O(n log k)
k smallest	max-heap	k	O(n log k)
kth largest, one shot	quickselect	—	O(n) average
all sorted	heapify plus n pops	n	O(n log n)
running median	two heaps	n/2 each	O(log n) per insert

Merging K Sorted Sequences

Keep one candidate from each source in the heap. This is the k-way merge, and it is also how external sorting works.

import heapq

def merge_k_sorted_lists(lists):
    """lists is a list of sorted arrays. O(N log k) for N total elements."""
    h = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(h)
    out = []
    while h:
        val, li, idx = heapq.heappop(h)
        out.append(val)
        if idx + 1 < len(lists[li]):
            heapq.heappush(h, (lists[li][idx + 1], li, idx + 1))
    return out

def merge_k_linked_lists(heads):
    """Linked-list version. Push (val, tiebreak, node)."""
    import itertools
    tie = itertools.count()
    h = [(n.val, next(tie), n) for n in heads if n]
    heapq.heapify(h)
    dummy = tail = ListNode()
    while h:
        _, _, node = heapq.heappop(h)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(h, (node.next.val, next(tie), node.next))
    return dummy.next

Two Heaps For A Running Median

A max-heap holds the lower half, a min-heap the upper half. Rebalance so the sizes differ by at most one.

import heapq

class MedianFinder:
    """add O(log n), median O(1)."""
    def __init__(self):
        self.low = []      # max-heap via negation, the smaller half
        self.high = []     # min-heap, the larger half

    def add(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))   # pass the max up
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2.0

The unconditional push-then-transfer is what keeps the two halves correctly ordered without any comparison branch.

Heapsort And Task Scheduling

def heapsort(a):
    """O(n log n) guaranteed, O(1) extra with an in-place sift-down."""
    import heapq
    heapq.heapify(a)
    return [heapq.heappop(a) for _ in range(len(a))]

def schedule_meeting_rooms(intervals):
    """Minimum rooms needed. Heap of end times. O(n log n)."""
    import heapq
    intervals.sort(key=lambda x: x[0])
    ends = []
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)    # reuse the freed room
        else:
            heapq.heappush(ends, end)
    return len(ends)

Heaps also power Dijkstra, Prim's MST, A\*, and Huffman coding, all of which repeatedly need "the cheapest thing left".

Gotchas

heapq is min-only. Negate for a max-heap, and remember to negate the result back.
Only h[0] is ordered. The rest of the list is heap order, not sorted order. Printing the list looks wrong but is fine.
Negating floats is safe, negating strings is not. For max ordering on strings use a comparator language or reverse the sort key differently.
Iterating a Java PriorityQueue yields heap order. Poll repeatedly for sorted output.
C++ pop() returns void and top() on an empty heap is undefined behavior. Check empty() first.
Heaps cannot search or delete by value in O(log n) without a side index map. When you need that, use a balanced tree or lazy deletion (push tombstones and skip stale entries on pop).
Lazy deletion needs a validity check. Pop until the top is still current, otherwise stale entries corrupt the answer.
heapify beats repeated heappush. O(n) versus O(n log n) for the same result.
Tuple comparison falls through to later elements. That is a feature for tie-breaking and a TypeError when the payload is not comparable.