How do you find the k smallest elements in an array using a heap?

Method 1: Build a min-heap O(n), then extract-min k times O(k log n). Total O(n + k log n). Method 2: Use a max-heap of size k. Insert first k elements. For remaining n-k elements, if element < heap top, replace top and heapify. Total O(n log k). Method 2 is better when k << n.

Heaps & Priority Queues

Q: Why does building a heap from an array take O(n) and not O(n log n)?

Building a heap by calling heapify-down on each internal node from n/2 down to 1 takes O(n). The cost analysis: nodes at height h number at most n/2^(h+1), and each heapify-down at height h costs O(h). Summing: sum over h from 0 to log n of (n/2^(h+1))*h = O(n). This is better than inserting n elements one by one (O(n log n)).

Q: What is the time complexity of heap sort?

Heap sort: O(n) to build the heap, then O(n log n) for n extract-max operations (each O(log n)). Total: O(n log n). Space: O(1) since it sorts in-place. Unlike merge sort, heap sort is not stable. Unlike quicksort, heap sort has guaranteed O(n log n) worst case.

Q: What is a d-ary heap?

A d-ary heap is a heap where each node has at most d children (binary heap has d=2). Height = log_d(n). Insert: O(log_d(n)). Extract-max/min: O(d * log_d(n)) because heapify-down compares d children. Increasing d reduces height (faster insert) but increases per-level work (slower extract). Optimal d depends on the application.

Max-heap, heapify, heap sort, O(n) build-heap proof — high-precision GATE topic tested with array-state questions and complexity proofs.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways

Max-heap: parent ≥ children. Min-heap: parent ≤ children. Complete binary tree stored as an array.
Array index rules: parent of i = ⌊i/2⌋, left child = 2i, right child = 2i+1 (1-indexed).
Insert: add at end, heapify-up. O(log n).
Extract-max: swap root with last, reduce size, heapify-down. O(log n).
Build-heap (heapify all internal nodes bottom-up): O(n) — not O(n log n).
Heap sort: O(n) build + O(n log n) extractions = O(n log n). In-place, not stable.
Priority queue: abstract data type; typically implemented with a heap.

1. Heap Definition & Array Representation

A heap is a complete binary tree satisfying the heap property:

Max-heap: A[parent] ≥ A[child] for all nodes.
Min-heap: A[parent] ≤ A[child] for all nodes.

Array representation (1-indexed):
Parent of node i: ⌊i/2⌋
Left child of i: 2i
Right child of i: 2i+1
Last internal (non-leaf) node: ⌊n/2⌋

0-indexed: Parent = ⌊(i−1)/2⌋, Left = 2i+1, Right = 2i+2

A max-heap of size n: root = maximum element. A min-heap: root = minimum element.

2. Heap Operations

Insert (heapify-up / sift-up)

1. Place new element at position n+1 (end).
2. Compare with parent; if larger (max-heap), swap.
3. Repeat until heap property restored or root reached.
Time: O(log n)

Extract-Max (heapify-down / sift-down)

1. Save root (max element).
2. Move last element to root; reduce heap size by 1.
3. Compare root with its children; swap with the larger child if larger.
4. Repeat until heap property restored.
Time: O(log n)

Decrease-Key / Increase-Key

Decrease a key (min-heap context): update value, heapify-up. O(log n). Used in Dijkstra’s algorithm.

Delete arbitrary node

Decrease key to −∞ (sift-up to root), then extract-min. O(log n).

Operation	Time
Insert	O(log n)
Extract-max/min	O(log n)
Peek (max/min)	O(1)
Build-heap	O(n)
Decrease-key	O(log n)
Search arbitrary	O(n)

3. Build-Heap: O(n) Proof

Build-heap calls heapify-down on all internal nodes from ⌊n/2⌋ down to 1.

Cost analysis:
Nodes at height h: at most ⌈n / 2^h+1⌉
Heapify-down at height h: O(h)
Total cost = ∑_h=0^{⌊log n⌋} ⌈n/2^h+1⌉ × h
≤ n ∑_h=0^∞ h/2^h = n × 2 = O(n)
(using ∑ h x^h = x/(1−x)² for |x|<1, x=1/2)

Build-heap = O(n), NOT O(n log n)

This is a frequent GATE question: “What is the time complexity of building a heap from n elements?” Answer: O(n).

4. Heap Sort

Algorithm:
1. Build max-heap from input array: O(n)
2. For i = n down to 2:
swap A[1] (max) with A[i]
heapify-down on reduced heap of size i−1: O(log i)
Total: O(n) + O(n log n) = O(n log n)

Property	Heap Sort	Merge Sort	Quick Sort
Time (avg)	O(n log n)	O(n log n)	O(n log n)
Time (worst)	O(n log n)	O(n log n)	O(n²)
Space	O(1)	O(n)	O(log n)
Stable	No	Yes	No (usually)
In-place	Yes	No	Yes

5. Priority Queue

A priority queue is an abstract data type where each element has a priority. The element with the highest (or lowest) priority is served first. Typically implemented with a binary heap.

Applications: Dijkstra’s shortest path, Prim’s MST, Huffman encoding, A* search, CPU task scheduling.

6. d-ary Heaps

Each node has up to d children. Stored in array: children of i at positions di−(d−2), di−(d−3), ..., di+1 (1-indexed).

Height: log_d(n)
Insert (heapify-up): O(log_dn)
Extract-min/max (heapify-down): O(d × log_dn) — compare d children at each level

Trade-off: Higher d → shorter height → faster insert; but heapify-down does more comparisons per level.

7. GATE CS Solved Examples

Example 1 — Heap array state after insertion (GATE CS 2021)

Q: Insert 5, 3, 17, 10, 84, 19, 6, 22, 9 into an empty max-heap (in this order). What is the heap array?

Solution (trace key steps):

Insert 5: [5]
Insert 3: [5, 3]
Insert 17: [5, 3, 17] → 17 > parent 5 → swap → [17, 3, 5]
Insert 10: [17, 3, 5, 10] → 10 > parent 3 → swap → [17, 10, 5, 3]
Insert 84: [17, 10, 5, 3, 84] → 84>10 → [17, 84, 5, 3, 10] → 84>17 → [84, 17, 5, 3, 10]
Insert 19: [84, 17, 5, 3, 10, 19] → 19>5 → [84, 17, 19, 3, 10, 5]
Insert 6: [84, 17, 19, 3, 10, 5, 6]
Insert 22: [84, 17, 19, 3, 10, 5, 6, 22] → 22>3 → [84, 17, 19, 22, 10, 5, 6, 3] → 22>17 → [84, 22, 19, 17, 10, 5, 6, 3]
Insert 9: [84, 22, 19, 17, 10, 5, 6, 3, 9]

Final heap: [84, 22, 19, 17, 10, 5, 6, 3, 9]

Example 2 — Build-heap complexity (GATE CS 2018)

Q: What is the number of comparisons to build a max-heap from n arbitrary elements?

Answer: O(n) comparisons. The tight bound is 2n − 2⌊log n⌋ − 2 comparisons in the worst case.

Example 3 — k-th smallest (GATE CS 2016)

Q: Find the 3rd smallest element among [4, 7, 2, 9, 1, 5, 8]. Use a heap approach.

Solution: Build min-heap: [1, 4, 2, 9, 7, 5, 8]. Extract-min 3 times: 1st = 1 (heap becomes [2,4,5,9,7,8]), 2nd = 2 (heap: [4,7,5,9,8]), 3rd = 4.

3rd smallest = 4. Cost: O(n) + O(3 log n) = O(n).

8. Common Mistakes

Mistake 1 — Build-heap is O(n log n)

Wrong. Bottom-up build-heap is O(n). Top-down (inserting one by one) is O(n log n). GATE always tests this distinction.

Mistake 2 — Wrong parent/child index

1-indexed: parent = i/2, children = 2i and 2i+1. 0-indexed: parent = (i-1)/2, children = 2i+1 and 2i+2. Mixing them causes off-by-one errors.

Mistake 3 — Heap sort sorts in descending order for max-heap

Wrong. Using a max-heap and extracting max repeatedly places the largest element at the end → ascending order.

Mistake 4 — Heap supports O(1) search

Heap only gives O(1) access to min/max. Searching for an arbitrary element requires O(n) scan. Heap is not ordered like a BST.

Mistake 5 — d-ary heap extract is O(log n)

Extract-min in a d-ary heap is O(d × log_dn) because you compare d children at each sift-down step. Only insert is O(log_dn).

9. FAQ

Why does building a heap from an array take O(n) and not O(n log n)?

Bottom-up heapify: most nodes are near the bottom and have small subtrees. The sum of work across all nodes converges to O(n) (geometric series proof). One-by-one insertion is O(n log n).

What is the time complexity of heap sort?

O(n log n) always. O(n) build-heap + O(n log n) n extractions. In-place, O(1) space. Not stable.

How do you find the k smallest elements using a heap?

Min-heap: O(n) build + O(k log n) extractions. Max-heap of size k: O(n log k) for streaming approach. Use max-heap-of-k when k << n.

What is a d-ary heap?

Each node has d children. Height log_dn. Insert: O(log_dn). Extract: O(d log_dn). Higher d = faster inserts, slower extracts.

Heaps and Priority Queues – Data Structures | GATE CS