Heaps and priority queues

In short

A heap is a complete binary tree stored in an array that keeps one simple rule - every parent is better than (or equal to) its children - so the best element is always at the root and reachable in O(1). A priority queue is the abstract data type (insert, find-min/max, delete-min/max, decrease-key) and a binary heap is its standard implementation, giving O(log n) updates with no pointers and no wasted memory. The pair is examined every year in GATE CS (heapify cost, build-heap derivation, heap-sort comparisons, array-index arithmetic) and in university Data Structures papers. In placement rounds it is the expected answer for "k largest elements", "merge k sorted lists", "running median" and "task scheduler", asked at Amazon, Microsoft, Google, Flipkart, Walmart, Oracle, Zoho, Adobe, Goldman Sachs, Samsung R&D and almost every product company hiring from Indian campuses.

Explained

Definitions and the two heap properties

• Complete binary tree: all levels full except possibly the last, which is filled left to right. This shape is what allows array storage with no gaps.
• Max-heap property: for every node i, key(parent(i)) ≥ key(i). Min-heap property: key(parent(i)) ≤ key(i). The property is between parent and child only - not between siblings and not left-to-right.
• Therefore the root holds the global maximum (max-heap) or minimum (min-heap); any root-to-leaf path is sorted, but the array as a whole is not sorted.
• A heap is partially ordered; a BST is totally ordered by in-order traversal. Searching an arbitrary key in a heap is O(n) - there is no left/right decision rule.
• Height of a heap with n nodes = ⌊log₂ n⌋; number of leaves = ⌈n/2⌉; number of internal nodes = ⌊n/2⌋.
• Priority queue (ADT): a collection where each element has a priority and deletion always removes the highest-priority element. Operations: insert(x,p), peek(), extract(), decrease_key/increase_key, delete(i), merge.
• A priority queue is not FIFO. Two elements with equal priority may come out in any order unless stability is forced (see the tie-breaking trick in the examples).

Array representation (0-based and 1-based)

• 1-based (textbook/CLRS/GATE): parent(i) = ⌊i/2⌋, left(i) = 2i, right(i) = 2i+1, root at index 1, last internal node at ⌊n/2⌋.
• 0-based (C/C++/Java code): parent(i) = ⌊(i−1)/2⌋, left(i) = 2i+1, right(i) = 2i+2, root at index 0, last internal node at ⌊n/2⌋ − 1.
• Nodes at indices ⌊n/2⌋+1 … n (1-based) are all leaves - heapify is never called on them.
• Advantages of array storage: no pointer overhead, cache-friendly sequential access, O(1) index arithmetic instead of pointer chasing.
• Limitation: a fixed array must be resized (amortised doubling) and an element's position moves, so external references need an index map (position array) to support decrease-key.

The two core repair operations

sift-up (percolate-up / bubble-up) - used after insertion, when a node may be *better* than its parent:

1. Place the new key at the end of the array (index n, keeping the shape complete).
2. While the node is better than its parent, swap with the parent.
3. Stop at the root or when the property holds. Cost O(log n), at most ⌊log₂ n⌋ swaps.

sift-down (percolate-down / heapify / max-heapify) - used after deletion or during build, when a node may be *worse* than a child:

1. Find the better of the two children (largest child for a max-heap).
2. If that child is better than the node, swap and recurse/loop into the child's position.
3. Stop at a leaf or when the property holds. Cost O(log n), but two comparisons per level (child-vs-child, then node-vs-child).

insert(x): append + sift-up → O(log n) worst case, O(1) amortised/average for random keys (most inserts stop within a level or two). extract-max (delete root): return root, move the last element to the root, reduce size by 1, sift-down → O(log n) always. increase-key / decrease-key(i, new): change the key, then sift-up (max-heap increase, min-heap decrease) or sift-down (the opposite direction) → O(log n). Needs the element's index. delete(i): replace with the last element, shrink, then sift-up or sift-down depending on comparison → O(log n). peek / find-max: O(1), read index 1 (or 0). build-heap: sift-down on indices ⌊n/2⌋ down to 1 → O(n), not O(n log n).

Why build-heap is O(n) - derivation outline

• A node at height h costs O(h) to sift down; there are at most ⌈n/2^h+1⌉ nodes at height h.
• Total work T(n) = Σ(h = 0 to ⌊log n⌋) ⌈n/2^h+1⌉ · O(h) ≤ O(n) · Σ(h ≥ 0) h/2^h.
• The infinite series Σ h/2^h = (1/2)/(1 − 1/2)² = 2 (standard result Σ h·x^h = x/(1−x)² at x = ½).
• Hence T(n) ≤ 2·O(n) = O(n) - linear, because nearly half the nodes are leaves costing nothing and only one node is at full height.
• Contrast: inserting n keys one by one costs Θ(n log n) in the worst case (increasing order). Bottom-up build is the exam answer whenever all keys are available at once.
• Exact comparison counts (often asked): bottom-up build-heap uses at most 2n comparisons and at most n swaps; heap-sort as a whole uses about 2n log₂ n comparisons.

Heap sort

HEAPSORT(A, n):            # 1-based, ascending output using a MAX-heap
  BUILD-MAX-HEAP(A, n)     # O(n)
  for i = n down to 2:
      swap A[1], A[i]      # largest goes to its final place
      n' = i - 1
      MAX-HEAPIFY(A, 1, n')# O(log i)

• Ascending order needs a max-heap (and descending needs a min-heap) - a very common exam trap.
• Time: Θ(n log n) in best, average and worst cases; all-equal keys drop to Θ(n) in some variants but the standard analysis is Θ(n log n).
• Space: O(1) auxiliary - sorts in place; iterative heapify avoids the O(log n) recursion stack.
• Not stable (swaps move equal keys past each other). Not adaptive - nearly sorted input gives no speed-up.
• Versus quicksort: heap sort has a guaranteed O(n log n) worst case but poorer cache locality (jumps of 2i), so quicksort is usually 2-3× faster in practice. Introsort (C++ std::sort) starts with quicksort and switches to heap sort when recursion gets too deep - that is heap sort's real-world role.
• Versus merge sort: same O(n log n), but heap sort uses O(1) extra space while merge sort needs O(n) and is stable.

Variants: d-ary, binomial, Fibonacci, and other priority-queue implementations

• d-ary heap: each node has d children; height = Θ(log_d n). Insert/decrease-key O(log_d n) is faster, extract-min O(d·log_d n) is slower (d comparisons per level). d = 4 is often fastest in practice because of cache lines; used to speed up Dijkstra on dense graphs.
• Indices (0-based, d-ary): children of i are d·i+1 … d·i+d; parent(i) = ⌊(i−1)/d⌋.
• Binary heap cannot merge cheaply: merging two heaps of size n is O(n) (concatenate + build-heap). Mergeable heaps exist for this reason.
• Binomial heap: a forest of binomial trees B₀…B_k; merge/insert/extract-min O(log n), insert O(1) amortised. Mirrors binary addition of the sizes.
• Fibonacci heap: insert, merge, decrease-key O(1) amortised, extract-min O(log n) amortised. Gives Dijkstra its theoretical O(E + V log V) bound, but large constants and pointer overhead make it slower than a binary heap for typical competitive/industrial sizes.
• Leftist / skew heaps: pointer-based mergeable heaps, O(log n) merge; asked in some university syllabi.
• Min-max heap / double-ended priority queue: alternating min and max levels so both extremes are O(1) findable; interval heaps are an alternative.
• Treap / balanced BST as a priority queue: O(log n) for everything plus ordered traversal and arbitrary search - the price is pointers and constants.

\*O(1) if a pointer to the minimum root is cached.

Library support and standard patterns

• C++: std::priority_queue<int> is a max-heap by default; a min-heap is priority_queue<int, vector<int>, greater<int>>. Raw algorithms: make_heap, push_heap, pop_heap, sort_heap, is_heap on any random-access range. No decrease-key - erase-and-reinsert, or push a duplicate and skip stale entries ("lazy deletion").
• Java: java.util.PriorityQueue is a min-heap by default; pass a Comparator for max or custom order. offer/poll/peek are the operations; iteration order is not sorted. Not thread-safe (use PriorityBlockingQueue).
• Python: heapq provides a min-heap on a plain list - heappush, heappop, heapify (O(n)), heappushpop, heapreplace, nlargest, nsmallest. For a max-heap, push negated keys or wrap keys in a reversing class.
• Standard interview patterns: k largest → min-heap of size k; k smallest → max-heap of size k; running median → max-heap of the lower half + min-heap of the upper half, sizes balanced within 1; merge k sorted lists → min-heap of k heads; sliding-window maximum → heap with lazy deletion (or a deque in O(n)); top-k frequent → count map + heap of size k; interval/meeting-room scheduling → min-heap of end times.
• Operating systems and systems work: priority scheduling queues, timer/timeout wheels and event queues, Huffman coding, A* and Dijkstra open lists, bandwidth schedulers, load shedding.

Key points

• Heap - a complete binary tree satisfying the heap property; stored in an array with no pointers.
• Heap property - parent ≥ children (max-heap) or parent ≤ children (min-heap); nothing is implied between siblings.
• Priority queue - the ADT; heap - the usual implementation. Do not use the words interchangeably in an interview.
• Indices (1-based) - parent ⌊i/2⌋, children 2i and 2i+1; (0-based) - parent ⌊(i−1)/2⌋, children 2i+1 and 2i+2.
• Height - ⌊log₂ n⌋; leaves occupy indices ⌊n/2⌋+1 … n, so ⌈n/2⌉ nodes need no heapify.
• sift-up - fixes a node that is too good for its parent (insert); one comparison per level.
• sift-down - fixes a node that is too bad for its children (delete/build); two comparisons per level.
• insert - O(log n) worst, O(1) average; extract - O(log n); peek - O(1); search arbitrary key - O(n).
• build-heap bottom-up - O(n); n successive inserts - O(n log n). Know the series Σ h/2^h = 2 behind it.
• Heap sort - Θ(n log n) in all cases, O(1) extra space, in-place, not stable, not adaptive; needs a max-heap for ascending output.
• Binary heap merge - O(n); use binomial or Fibonacci heaps when merge or decrease-key dominates.
• Fibonacci heap - O(1) amortised insert/decrease-key, powering the O(E + V log V) Dijkstra bound; practically slower than a binary heap.
• d-ary heap - shallower tree: cheaper decrease-key, costlier extract-min; d = 4 is a common practical choice.
• Decrease-key needs an index map (element → array position), otherwise it degenerates to an O(n) search.
• Lazy deletion - push the updated entry and discard stale pops; the standard trick in languages without decrease-key.
• Library defaults - C++ priority_queue max-heap, Java PriorityQueue and Python heapq min-heap.
• k-th largest in n elements - min-heap of size k, O(n log k) time and O(k) space; beats sorting when k is small.
• A heap is not a BST - in-order traversal of a heap is meaningless, and a sorted array is a valid min-heap but a heap array is rarely sorted.

Formulas and examples

Example 1 - build a max-heap bottom-up from A = [4, 10, 3, 5, 1, 8, 2] (1-based, n = 7).

• Last internal node = ⌊7/2⌋ = 3. Heapify i = 3, 2, 1.
• i = 3 (key 3, children A[6]=8, A[7]=2): largest child 8 > 3 → swap. A = [4, 10, 8, 5, 1, 3, 2].
• i = 2 (key 10, children A[4]=5, A[5]=1): 10 is already largest → no change.
• i = 1 (key 4, children A[2]=10, A[3]=8): largest is 10 → swap → A = [10, 4, 8, 5, 1, 3, 2]; now at index 2 (key 4, children 5 and 1): 5 > 4 → swap → A = [10, 5, 8, 4, 1, 3, 2]; index 4 is a leaf → stop.
• Final max-heap: [10, 5, 8, 4, 1, 3, 2]. Swaps used = 3, under the n = 7 swap bound (8 comparisons, under 2n = 14). Root 10 is the maximum. Note the array is not sorted - that is correct.

Example 2 - insert 15, then extract-max from [10, 5, 8, 4, 1, 3, 2].

• Insert: append at index 8 → [10, 5, 8, 4, 1, 3, 2, 15]. parent(8) = 4 → 15 > 4, swap → index 4. parent(4) = 2 → 15 > 5, swap → index 2. parent(2) = 1 → 15 > 10, swap → index 1. Heap = [15, 10, 8, 5, 1, 3, 2, 4], 3 swaps (≤ ⌊log₂ 8⌋ = 3).
• Extract-max: return 15; move last element 4 to the root and set n = 7 → [4, 10, 8, 5, 1, 3, 2]. Sift-down: children 10 and 8 → swap with 10 → [10, 4, 8, 5, 1, 3, 2]; at index 2 children 5 and 1 → swap with 5 → [10, 5, 8, 4, 1, 3, 2]. Cost 2 swaps, 4 comparisons.

Example 3 - heap sort trace on [10, 5, 8, 4] (max-heap already valid, ascending output).

• Result [4, 5, 8, 10], obtained with 3 extractions (n − 1) and no extra array.

Example 4 - 3rd largest of [7, 10, 4, 3, 20, 15] with a size-3 min-heap.

• Push 7, 10, 4 → heap {4, 7, 10}, root (minimum) = 4.
• Next 3: 3 < root 4 → discard. Next 20: 20 > 4 → pop 4, push 20 → {7, 10, 20}, root = 7.
• Next 15: 15 > 7 → pop 7, push 15 → {10, 15, 20}, root = 10 → the 3rd largest is 10 (sorted desc: 20, 15, 10 ✓).
• Cost: 6 elements × log₂3 ≈ 6 × 1.58 ≈ 10 comparisons-worth of work, O(n log k) = O(6 log 3), versus O(n log n) for a full sort; memory held = 3 elements, not 6.

Example 5 - running median of the stream 5, 15, 1, 3 using two heaps.

• Keep lo = max-heap of the smaller half, hi = min-heap of the larger half, with |lo| − |hi| ∈ {0, 1}.
• 5 → lo = [5] → median 5.
• 15 → 15 > 5 so hi = [15]; sizes 1,1 → median (5 + 15)/2 = 10.
• 1 → 1 ≤ 5 so lo = [5, 1]; sizes 2,1 → median = top of lo = 5.
• 3 → 3 ≤ 5 so lo = [5, 3, 1]; sizes 3,1 unbalanced → pop 5 from lo into hi → lo = [3, 1], hi = [5, 15]; sizes 2,2 → median = (3 + 5)/2 = 4.
• Each insert is O(log n); each median query O(1).

Example 6 - stable / tie-broken priority queue. Push the tuple (priority, counter, payload) with a monotonically increasing counter. Equal priorities then compare by insertion order, making the queue FIFO within a priority class - the standard fix in Python heapq and Java comparators, and also prevents TypeError when payloads are not comparable.

import heapq
h, seq = [], 0
for pr, task in [(2,"backup"), (1,"alert"), (2,"report")]:
    heapq.heappush(h, (pr, seq, task)); seq += 1
while h:
    print(heapq.heappop(h)[2])   # alert, backup, report

Where it is used

• Graph and route engines: Dijkstra and A* open lists in Ola/Uber/Rapido ETA and routing, Google/MapmyIndia navigation, IRCTC-style shortest-path and fare queries, Zomato/Swiggy/Dunzo delivery dispatch.
• Operating systems, databases and networks: CPU priority scheduling, kernel timer queues (timerfd, timeout wheels), Linux CFS-style run queues, external merge sort and top-N query operators in PostgreSQL/MySQL, QoS and packet schedulers in telecom gear (Reliance Jio, Airtel networks, Tejas Networks equipment).
• Streaming and analytics: top-k trending items, leaderboards (Dream11, MPL), real-time percentile/median monitoring in SRE dashboards, Kafka/Flink windowed aggregation, Elasticsearch top-hits.
• Fintech and exchanges: order-matching engines at NSE/BSE and broking platforms (Zerodha, Groww, Upstox) use price-time priority queues; payment retry and settlement queues at NPCI-connected PSPs; risk-alert prioritisation.
• Compression, ML and simulation: Huffman coding in ZIP/JPEG/MP3, beam search in NLP decoders, event-driven simulation (queueing and manufacturing models), k-nearest-neighbour searches.
• Job roles: SDE and backend developer interviews (DSA rounds), competitive programming (CodeChef/Codeforces, ICPC Amritapuri), GATE CS preparation, systems/SRE roles tuning schedulers, and quant/low-latency engineering.

Interview questions

• Q: What is the difference between a heap and a priority queue? A: A priority queue is an abstract data type defined by its operations; a heap is a concrete data structure that implements it efficiently. A priority queue can also be built from a sorted list or a balanced BST.
• Q: Why is bottom-up build-heap O(n) and not O(n log n)? A: Cost depends on a node's height, and ⌈n/2⌉ nodes are leaves of height 0; summing ⌈n/2^h+1⌉·h over all heights converges because Σ h/2^h = 2, giving linear total work.
• Q: For ascending heap sort, do you use a min-heap or a max-heap? A: A max-heap - you repeatedly swap the root with the current last element, so the largest values accumulate at the right end in sorted order.
• Q: Is heap sort stable, and is quicksort usually faster? A: Heap sort is not stable because sifting swaps equal keys past one another; quicksort is typically 2-3× faster due to better cache locality, though heap sort guarantees O(n log n).
• Q: How do you find the k-th largest element in an array of n numbers? A: Maintain a min-heap of size k; push each element and pop when the size exceeds k. The root is the answer, in O(n log k) time and O(k) space.
• Q: Can you search for an arbitrary element in a heap in O(log n)? A: No - a heap gives no ordering between siblings or subtrees, so arbitrary search is O(n). Keep a hash map from key to index if you need fast lookup or decrease-key.
• Q: How would you implement decrease-key without library support? A: Either maintain a position map updated on every swap, or use lazy deletion - push the new (smaller) entry and skip entries you recognise as stale when they are popped.
• Q: How do you merge two binary heaps of sizes m and n? A: Concatenate the arrays and run build-heap, giving O(m + n). If merging is frequent, use a binomial, leftist or Fibonacci heap with O(log n) or O(1) merge.
• Q: Where does a Fibonacci heap actually help? A: In algorithms dominated by decrease-key, such as Dijkstra and Prim, where it lowers the bound to O(E + V log V); in practice, constants and pointer overhead often make a binary heap faster.
• Q: Is a sorted array a valid heap? A: An array sorted ascending is a valid min-heap and one sorted descending is a valid max-heap, but the converse is false - a valid heap is generally unsorted.
• Q: What are the minimum and maximum number of nodes in a heap of height h? A: Minimum 2^h (last level has one node) and maximum 2^h+1 − 1 (perfect tree), with height measured in edges from root to deepest leaf.
• Q: Find the running median of a data stream. A: Keep a max-heap of the lower half and a min-heap of the upper half, rebalanced so their sizes differ by at most one; the median is the top of the larger heap, or the average of both tops when sizes are equal.
• Q: Which is faster for finding the top 10 of a billion records - sorting or a heap? A: A heap of size 10 - it is O(n log 10) time with O(10) memory and streams the data once, whereas sorting needs O(n log n) and the whole dataset in memory or on disk.

Common mistakes

• Mixing up 0-based and 1-based index formulas mid-solution, so children are computed as 2i and 2i+1 in a 0-based array.
• Using a min-heap for ascending heap sort, then being unable to explain the output order.
• Claiming build-heap is O(n log n), or applying the O(n) bound to n separate insertions - inserting n keys one at a time is Θ(n log n).
• Calling sift-up after deleting the root (the moved element is too small, so it must sift down), or sift-down after an insertion.
• Forgetting to decrement the heap size before heapifying in extract/heap-sort, so the already-sorted tail gets pulled back in.
• Assuming a heap is sorted, or doing an in-order traversal / binary search on a heap array.
• Treating a priority queue as FIFO for equal priorities, and forgetting the insertion-counter tie-breaker.
• Forgetting that C++ priority_queue is a max-heap while Java and Python default to min-heaps, which silently inverts the answer.

Related topics

Trees and binary search trees · Balanced trees: AVL, red-black and B-trees · Graphs and their representation · Sorting algorithms and their analysis · Hashing and hash tables · Greedy algorithms (Huffman, Dijkstra, Prim)