Heap & Priority QueueHeaps & Priority Queues

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

A sorted array answers “what is the smallest element?” in O(1) but costs O(n) to insert into. A plain list answers insertion in O(1) but costs O(n) to find the minimum. A balanced BST does both in O(log n), but you are paying for a total ordering you did not ask for.

A heap is the structure for the case where you only ever need one end of the ordering: the smallest element, or the largest, repeatedly. It gives you O(1) peek at the extreme, O(log n) insert, O(log n) extract, and — the part that surprises people — O(n) to build one from an unsorted array. It does all of this with no pointers at all, stored in a flat array, which makes it one of the most cache-friendly structures in this whole knowledge base.

The abstract operation a heap implements is the priority queue: an ADT where elements are dequeued in priority order rather than insertion order. That ADT is everywhere in real systems:

• Dijkstra’s algorithm and A* repeatedly extract the nearest unvisited node — see ./14-shortest-path-algorithms.md.
• Prim’s algorithm repeatedly extracts the cheapest edge crossing the cut — see ./15-minimum-spanning-trees.md.
• OS schedulers pick the highest-priority runnable task.
• Event simulation processes the next event by timestamp.
• Huffman coding repeatedly merges the two least-frequent symbols.
• Rate limiters, timers, and job queues fire the soonest-due item.
• heapq.merge, external sorting, and LSM-tree compaction merge k sorted runs by repeatedly taking the smallest head.
• Streaming top-k and running median keep a bounded window of the interesting elements.

A common source of confusion first: “heap” here has nothing to do with “the heap” in memory management. The dynamic allocation region and this data structure share a name for historical reasons and are otherwise unrelated.

Fundamentals

The heap property

A binary heap is a complete binary tree (see ./10-tree-data-structures.md) satisfying one local invariant:

• Min-heap: every node’s key is ≤ both of its children’s keys. The minimum is therefore at the root.
• Max-heap: every node’s key is ≥ both of its children’s keys. The maximum is at the root.

That is the entire invariant. Note how weak it is compared to a BST:

A valid min-heap:                    NOT a BST, and that's fine:

           (1)                       - 3 is in 1's left subtree and 8 is in
          /   \                        1's right subtree, but 3 > ... nothing.
       (3)     (2)                   - There is no ordering between siblings.
       / \     / \                   - In-order traversal gives 7 3 5 1 8 2 9,
    (7)  (5) (8) (9)                   which is not sorted.

A heap is only partially ordered: it knows relationships along root-to-leaf paths and nothing about left-right relationships. That is precisely why it is cheaper than a BST — it does less work because it promises less. You cannot search a heap for an arbitrary key in better than O(n), and you cannot iterate it in sorted order without destroying it.

The implicit array — a tree with no pointers

Because a heap is a complete binary tree, its nodes can be numbered level by level with no gaps, and stored in a flat array. The parent/child relationships become arithmetic:

              index 0
                (1)
              /     \
        index 1     index 2
          (3)         (2)
         /   \       /   \
       (7)   (5)   (8)   (9)
        3     4     5     6

array:  [ 1,  3,  2,  7,  5,  8,  9 ]
index:    0   1   2   3   4   5   6

For 0-based indexing:

(Some textbooks use 1-based indexing, where the formulas are the slightly prettier 2i, 2i+1, and i // 2. Always check which convention a source uses before transcribing.)

This layout is the heap’s second big advantage after its complexity:

• Zero pointer overhead. A BST node costs a value plus two pointers (16 bytes of overhead on a 64-bit machine); a heap element costs the value alone.
• Excellent cache locality. The top few levels of the heap — the ones touched on every single operation — occupy the first few dozen array slots, which stay in L1 cache permanently. A pointer-based tree scatters those same nodes across the address space.
• No allocation per element. Growth is amortized O(1) array append (see ./04-arrays.md).

The catch is that it only works because the tree is complete. A general binary tree stored this way would need 2^h slots for h levels, which is why this trick is specific to heaps.

Sift-up and sift-down

Every heap operation is one of two repair routines. Both walk a single root-to-leaf path, so both are O(log n).

Sift-up (also called bubble-up, percolate-up, sift-down in CPython’s confusing internal naming) fixes a node that may be too small for its position — used after appending a new element at the end:

push 0 into [1, 3, 2, 7, 5, 8, 9]:

append at index 7:          0 < parent 7 -> swap:      0 < parent 3 -> swap:
        (1)                        (1)                        (1)
       /   \                      /   \                      /   \
    (3)     (2)                (3)     (2)                (0)     (2)
    / \     / \                / \     / \                / \     / \
  (7) (5) (8) (9)            (0) (5) (8) (9)            (3) (5) (8) (9)
  /                          /                          /
(0)                        (7)                        (7)

                                                   0 < parent 1 -> swap -> done

Sift-down (bubble-down, percolate-down, heapify) fixes a node that may be too large for its position — used after moving the last element to the root during a pop:

pop from [1, 3, 2, 7, 5, 8, 9]:  take 1, move last (9) to the root, sift down.

        (9)          9 > min(3,2)=2       (2)         9 > min(8,9)=8      (2)
       /   \         -> swap with 2      /   \        -> swap with 8     /   \
    (3)     (2)      ============>    (3)     (9)     ===========>    (3)     (8)
    / \     /                         / \     /                       / \     /
  (7) (5) (8)                       (7) (5) (8)                     (7) (5) (9)

The crucial detail in sift-down: you must compare against the smaller of the two children (for a min-heap). Swapping with the larger child would put a value above a smaller value and break the invariant immediately. This is the single most common bug in a hand-written heap.

class MinHeap:
    """A binary min-heap over a flat Python list. No pointers, no nodes."""

    def __init__(self):
        self.a = []

    def __len__(self):
        return len(self.a)

    def peek(self):
        """The minimum. O(1) — it is just a[0]."""
        return self.a[0]

    def push(self, item):
        """Append at the end, then sift up. O(log n)."""
        self.a.append(item)
        self._sift_up(len(self.a) - 1)

    def pop(self):
        """Remove and return the minimum. O(log n)."""
        last = self.a.pop()
        if not self.a:
            return last               # the heap had exactly one element
        top = self.a[0]
        self.a[0] = last              # move the last leaf to the root...
        self._sift_down(0)            # ...and let it sink back to its level
        return top

    def _sift_up(self, i):
        """Move a[i] up while it is smaller than its parent."""
        item = self.a[i]
        while i > 0:
            parent = (i - 1) // 2
            if self.a[parent] <= item:
                break                 # heap property restored
            self.a[i] = self.a[parent]    # shift the parent down; no full swap needed
            i = parent
        self.a[i] = item              # single write at the final resting place

    def _sift_down(self, i):
        """Move a[i] down while it is larger than its SMALLEST child."""
        n = len(self.a)
        item = self.a[i]
        while True:
            left = 2 * i + 1
            if left >= n:
                break                 # a[i] is a leaf
            right = left + 1
            child = left
            if right < n and self.a[right] < self.a[left]:
                child = right         # pick the smaller child — getting this wrong
                                      # silently breaks the invariant
            if item <= self.a[child]:
                break
            self.a[i] = self.a[child]
            i = child
        self.a[i] = item

    @classmethod
    def heapify(cls, items):
        """Build a heap from an arbitrary iterable in O(n) — see below."""
        h = cls()
        h.a = list(items)
        for i in range(len(h.a) // 2 - 1, -1, -1):
            h._sift_down(i)
        return h

Note the “hole” technique in _sift_up and _sift_down: instead of swapping on every step (three writes each), the code shifts the displaced element into place and writes the moving item exactly once at the end. Same complexity, roughly a third of the memory traffic. CPython’s heapq uses the same trick.

Why heapify is O(n), not O(n log n)

The naive way to build a heap from n items is n pushes, each O(log n), giving O(n log n). The heapify above does better: it calls _sift_down on every non-leaf node, from the last one backwards to the root, and runs in O(n).

The surprise resolves once you notice that _sift_down’s cost depends on the node’s height, not the tree’s, and almost every node is near the bottom.

In a heap of n nodes:

Summing the work:

    Total  =  Σ (n / 2^(k+1)) · k        for k = 0 .. h

           =  n · Σ  k / 2^(k+1)

                       ∞
    and the series     Σ  k / 2^(k+1)  converges to 1
                      k=0

    Total  ≈  n · 1  =  O(n)

The intuition without the algebra: half the nodes are leaves and do zero work; a quarter do at most one swap; an eighth do at most two. The nodes that could be expensive are exactly the nodes there are almost none of. The series 1/2 + 2/4 + 3/8 + 4/16 + … converges, so the total is linear.

Contrast with building the heap by sift-up instead (for i in range(n): sift_up(i)). That is O(n log n) and not linear, because sift-up’s cost depends on depth, and half the nodes are at maximum depth. Same tree, opposite direction, different complexity. This is a genuinely instructive pair — the asymmetry is entirely about which end of the tree the crowd is at.

Practically: heapq.heapify(a) is O(n); a loop of heapq.heappush is O(n log n). When you already have all the data, always heapify.

Complexity summary

The row that decides most designs is search: a heap cannot find an arbitrary element faster than a linear scan. If your workload needs both “give me the minimum” and “delete this specific element”, a bare heap is the wrong choice — you need a heap plus an index map, or a balanced BST, or the lazy-deletion pattern described below.

Key Concepts

Python’s heapq

Python has no heap class; heapq is a set of functions that operate on an ordinary list interpreted as a min-heap. This is the implementation you should use in production — it is written in C, well tested, and uses exactly the algorithms above.

import heapq

a = [5, 7, 9, 1, 3]

heapq.heapify(a)              # O(n) — in-place, a is now a valid min-heap
heapq.heappush(a, 4)          # O(log n)
smallest = heapq.heappop(a)   # O(log n) -> 1
peek = a[0]                   # O(1) — the minimum is always at index 0

# Fused operations: cheaper than the two calls, and they keep the size fixed
heapq.heappushpop(a, 6)       # push then pop — one sift-down, no growth
heapq.heapreplace(a, 6)       # pop then push — the item is NOT compared first

# Convenience helpers. O(n log k) with an internal size-k heap — good when
# k << n; if k is close to n, just call sorted().
heapq.nlargest(3, a)
heapq.nsmallest(3, a)

# k-way merge of already-sorted iterables. Lazy: O(1) memory per source,
# O(N log k) total. This is the core of external sorting and LSM compaction.
merged = list(heapq.merge([1, 4, 7], [2, 5, 8], [3, 6, 9]))

The distinction between heappushpop and heapreplace catches people out. heappushpop(h, x) returns min(x, h[0]) — if x is smaller than everything in the heap, it comes straight back out and the heap is untouched. heapreplace(h, x) always pops the current minimum first, then inserts x, so x can end up in the heap even if it is smaller than the item removed. For a “keep the k largest” loop, heappushpop is what you want.

Max-heaps in Python: the negation trick

heapq is min-only. There is no heapq.heapifymax in the public API. The standard workaround is to negate:

import heapq

max_heap = []
for value in [5, 1, 9, 3]:
    heapq.heappush(max_heap, -value)      # store the negation

largest = -heapq.heappop(max_heap)        # negate again on the way out -> 9
peek_largest = -max_heap[0]               # O(1)

Two caveats that bite in real code:

1. It only works for numbers. -x is undefined for strings, tuples, and most objects. For those, either wrap in a comparison-reversing class or push a (-priority, payload) tuple where only the numeric priority is negated.
2. Watch the asymmetry of the integer range in fixed-width languages. In Python, integers are arbitrary precision, so -x is always safe; in C/Java, -Integer.MIN_VALUE overflows back to itself. Worth knowing when porting.

The cleaner alternative when the payload is not comparable is to push tuples and let Python’s lexicographic tuple comparison do the work:

import heapq
import itertools

counter = itertools.count()               # a monotonically increasing tie-breaker
tasks = []

def add_task(priority, task):
    # (priority, insertion_order, payload)
    # The counter guarantees a total order, so `task` is NEVER compared.
    # Without it, two equal priorities would make Python compare the payloads,
    # which raises TypeError for objects that define no ordering.
    heapq.heappush(tasks, (priority, next(counter), task))

add_task(2, {"name": "send email"})
add_task(1, {"name": "pay invoice"})
add_task(2, {"name": "archive logs"})

priority, _, task = heapq.heappop(tasks)  # -> (1, ..., {'name': 'pay invoice'})

The itertools.count() tie-breaker is not optional decoration — it is the standard fix for the TypeError: '<' not supported between instances of 'dict' and 'dict' that a naive (priority, payload) heap throws the first time two priorities collide. It also makes the queue stable: equal priorities come out in insertion order.

The priority queue ADT

A priority queue is the abstract type; a binary heap is the usual implementation. The interface:

The last two are where binary heaps show their limits, and where the exotic heap variants earn their keep:

The Fibonacci heap row is a famous lesson in the gap between asymptotics and reality. It makes Dijkstra’s algorithm O(E + V log V) instead of O((V + E) log V), which is a real theoretical improvement — and it is almost never used, because its constant factors and pointer-chasing memory pattern make it slower than a binary heap on any input you will actually encounter. Know it exists; reach for heapq.

The decrease_key problem in Python. heapq has no decrease_key at all, because a flat list gives you no way to find an item’s index. The standard workaround is lazy deletion: push the new (better) entry without removing the old one, and discard stale entries when they surface.

import heapq

def dijkstra_style_loop(start, neighbours):
    """The lazy-deletion pattern every heapq-based Dijkstra uses."""
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                  # stale entry: a better path was found
                                      # after this one was pushed. Skip it.
        for v, w in neighbours(u):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))   # push a duplicate instead of
                                              # decreasing the old entry's key
    return dist

The heap can grow to O(E) entries rather than O(V), but each stale entry is discarded in O(1) and the total is still O(E log E) = O(E log V). This is the idiomatic Python approach and it is what you should write. See ./14-shortest-path-algorithms.md.

Heapsort

A heap gives a sorting algorithm almost for free: heapify the array, then repeatedly swap the root with the last element and shrink the heap by one.

def heapsort(a):
    """In-place, O(n log n) worst case, O(1) extra space, NOT stable."""
    n = len(a)

    def sift_down(i, size):
        # Max-heap version: sink a[i] while it is smaller than its largest child
        while True:
            left = 2 * i + 1
            if left >= size:
                return
            child = left
            right = left + 1
            if right < size and a[right] > a[left]:
                child = right
            if a[i] >= a[child]:
                return
            a[i], a[child] = a[child], a[i]
            i = child

    for i in range(n // 2 - 1, -1, -1):     # build a MAX-heap: O(n)
        sift_down(i, n)
    for end in range(n - 1, 0, -1):         # n-1 extractions: O(n log n)
        a[0], a[end] = a[end], a[0]         # largest goes to its final position
        sift_down(0, end)                   # restore the heap over a[0:end]
    return a

Heapsort’s O(n log n) worst case and O(1) space are strictly better guarantees than quicksort’s. It nonetheless loses to quicksort in practice because its access pattern (i → 2i+1) jumps around the array and destroys cache locality, while quicksort’s partition is two sequential scans. Its real production role is as the fallback in introsort (C++‘s std::sort): quicksort until the recursion gets suspiciously deep, then switch to heapsort to guarantee O(n log n). See ./08-sorting-algorithms.md.

The two-heaps pattern: running median

The problem: numbers arrive one at a time from a stream, and after each one you must report the median. Re-sorting is O(n log n) per element. Inserting into a sorted list is O(n) per element. The two-heaps pattern makes it O(log n) insert and O(1) median.

The idea: split the data at the median into two halves, and keep each half in the heap that puts its boundary at the top.

        max-heap "low"                          min-heap "high"
     (lower half of the data)                (upper half of the data)

              (8)   <- largest of the low half     (10)  <- smallest of the high half
             /   \                                /    \
          (5)     (7)                          (12)    (11)
          / \                                  /
       (2) (3)                              (15)

    The two roots straddle the median. If the sizes are equal, the median is
    their average; if `low` has one extra, the median is low's root.

The invariants to maintain after every insert:

1. Order: every element in low ≤ every element in high.
2. Balance: len(low) - len(high) is 0 or 1.

import heapq


class MedianFinder:
    """Running median over a stream. add() is O(log n), median() is O(1)."""

    def __init__(self):
        self.low = []      # max-heap of the lower half, stored negated
        self.high = []     # min-heap of the upper half

    def add(self, num):
        # Three lines, and they maintain both invariants unconditionally:
        # 1. Always push into `low` first (so `low` is the default larger half).
        heapq.heappush(self.low, -num)
        # 2. Move low's largest across to `high`. This guarantees the ORDER
        #    invariant: whatever ends up on top of `low` is now <= high's root.
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # 3. If that made `high` bigger, move its smallest back — restores BALANCE.
        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])              # odd count: low's root
        return (-self.low[0] + self.high[0]) / 2    # even count: average the roots

The three-line add is worth studying. The naive version — “compare against the roots, decide which heap to push into, then rebalance” — needs four or five branches and is easy to get subtly wrong on the empty-heap and equal-value edge cases. Pushing unconditionally into low, immediately shipping the top across to high, and then rebalancing back if needed handles every case with no conditionals except the final size check.

Where the pattern generalizes. Any time you need to maintain a split point over a dynamic multiset — the median, a percentile, “the k-th largest so far”, “is the current window balanced” — two heaps facing each other across the boundary is the tool. Variants:

• Sliding-window median: same structure plus lazy deletion (a dict of counts of elements pending removal, purged from the heap tops as they surface).
• IPO / task-scheduling problems: a max-heap of available items by profit and a min-heap of unavailable items by unlock time.
• Percentiles other than 50%: change the balance invariant from |low| − |high| ∈ {0,1} to whatever ratio you need.

Finding the k-th largest element

A classic problem with three good answers and one bad one.

import heapq
import random


# ---- Approach 1: sort. O(n log n) time, O(n) or O(1) space. -----------------
def kth_largest_sort(nums, k):
    """Simplest and often fastest for small n — Timsort has excellent constants."""
    return sorted(nums, reverse=True)[k - 1]


# ---- Approach 2: a size-k min-heap. O(n log k) time, O(k) space. ------------
def kth_largest_heap(nums, k):
    """
    Keep only the k largest seen so far. The heap's root is the SMALLEST of
    those k, which is exactly the k-th largest overall once the stream ends.
    """
    heap = nums[:k]
    heapq.heapify(heap)                   # O(k)
    for x in nums[k:]:
        if x > heap[0]:                   # O(1) reject — most elements land here
            heapq.heapreplace(heap, x)    # O(log k): pop the smallest, push x
    return heap[0]

# Equivalent one-liner in the standard library (same O(n log k) algorithm):
#   heapq.nlargest(k, nums)[-1]


# ---- Approach 3: quickselect. O(n) average, O(n^2) worst, O(1) space. -------
def partition(a, lo, hi):
    """Lomuto partition with a random pivot; returns the pivot's final index."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]             # randomization defeats adversarial input
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i


def quickselect(a, k):
    """k-th SMALLEST (0-indexed). Destroys the order of `a`."""
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        p = partition(a, lo, hi)
        if k == p:
            return a[k]
        if k < p:
            hi = p - 1        # recurse into ONE side only — this is why it's O(n)
        else:
            lo = p + 1


def kth_largest_quickselect(nums, k):
    """k-th largest = (n - k)-th smallest, 0-indexed."""
    return quickselect(list(nums), len(nums) - k)

The comparison:

Two things worth noting:

Why quickselect is O(n). Quicksort recurses into both halves, giving T(n) = 2T(n/2) + O(n) = O(n log n). Quickselect recurses into only the half that can contain the answer, giving T(n) = T(n/2) + O(n), and the geometric series n + n/2 + n/4 + … = 2n sums to O(n). The random pivot is what makes the O(n²) worst case (always picking the extreme) astronomically unlikely rather than triggerable by sorted input. See ./20-brute-force-greedy-and-randomised-algorithms.md and ./19-recursion-and-divide-and-conquer.md.

Why the heap approach wins in practice more often than the table suggests. Quickselect is asymptotically better but needs the entire array in memory and mutates it. The size-k heap works on a stream of unknown length, uses O(k) memory regardless of n, and — because of the if x > heap[0] guard — performs a cheap O(1) rejection for the vast majority of elements. For “top 10 trending items out of 100 million events”, the heap is not just easier, it is the only one of the two that runs at all.

k-way merge

The other everyday application of a heap: merging k already-sorted sequences into one sorted output. Take the smallest head across all k sequences, emit it, advance that sequence, repeat. A heap of size k makes “smallest head” an O(log k) question.

import heapq

def k_way_merge(sorted_lists):
    """
    O(N log k) where N is the total element count. Compare with concatenating
    everything and sorting: O(N log N). When k is small and N is huge, the
    difference is real — and unlike sorting, this is streaming.
    """
    heap = []
    for list_index, lst in enumerate(sorted_lists):
        if lst:
            # (value, which list, position in that list)
            heapq.heappush(heap, (lst[0], list_index, 0))

    out = []
    while heap:
        value, list_index, pos = heapq.heappop(heap)
        out.append(value)
        next_pos = pos + 1
        if next_pos < len(sorted_lists[list_index]):
            heapq.heappush(heap, (sorted_lists[list_index][next_pos], list_index, next_pos))
    return out


# In production, use the standard library — it is lazy, so it never
# materializes the full output and works on files, generators, and DB cursors:
#   heapq.merge(*sorted_iterables, key=None, reverse=False)

This is the merge step of external sorting (sort chunks that fit in RAM, write them out, then k-way merge the files), the compaction step of LSM-tree storage engines like RocksDB and Cassandra, and the way a distributed query engine combines sorted partial results from k shards. See ../../data-engineer/en/10-big-data-and-distributed-computing.md.

Best Practices

• Use heapq, not a hand-rolled heap. It is C-implemented, correct, and uses the hole-shifting optimization. Write your own once to understand sift-up/sift-down, then never again.
• heapify when you have all the data; heappush in a loop only when you do not. O(n) versus O(n log n) for the identical result.
• Always add a tie-breaker to tuple entries. (priority, itertools.count(), payload). Without it, equal priorities make Python compare the payloads, which raises TypeError for anything without a defined ordering — and it will not fail until the first priority collision in production.
• Negate for a max-heap, but only with numbers. For non-numeric keys, negate just the numeric priority in a tuple, or wrap the item in a class with __lt__ reversed.
• Do not use a heap when you need to search or delete arbitrary elements. That is O(n) in a heap. Use a balanced BST, a SortedList, or a heap paired with an index dictionary.
• Use lazy deletion for decrease_key. Push the improved entry and skip stale ones on pop (if d > dist[u]: continue). This is the standard Python Dijkstra idiom and it is asymptotically fine.
• For “top k”, bound the heap at size k. heapq.nlargest(k, iterable) or a manual size-k min-heap gives O(n log k) time and O(k) memory — critical when n does not fit in RAM.
• Prefer heappushpop over heappush + heappop. One sift-down instead of two heap operations, and the heap never grows past its target size.
• Reach for two heaps whenever you must maintain a dynamic split point. Running median, percentiles, “cheapest available vs. soonest unlocked” — the boundary-facing pair is the pattern.
• Do not sort just to find one extreme. min(a) is O(n); sorted(a)[0] is O(n log n). Similarly, do not sort just to find the k-th element — use quickselect or a bounded heap.
• Remember heapsort’s real job. As a standalone sort it loses to quicksort and Timsort on cache behaviour, but its O(n log n) worst case and O(1) space make it the right safety net inside introsort.
• heapq is not thread-safe. Guard it with a lock, or use queue.PriorityQueue, which wraps heapq with the locking already done.

References

• roadmap.sh — Data Structures & Algorithms
• Heap (data structure) — Wikipedia
• Binary heap — Wikipedia
• Priority queue — Wikipedia
• Heapsort — Wikipedia
• Quickselect — Wikipedia
• Fibonacci heap — Wikipedia
• Python Documentation — heapq: Heap queue algorithm
• Python Documentation — queue.PriorityQueue
• CLRS — Introduction to Algorithms, Chapter 6: Heapsort
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• VisuAlgo — Binary Heap visualization
• Big-O Cheat Sheet