Heap questions in GATE CS are mechanical, numerical, and worth easy marks if you can execute three procedures without slipping: heapify, build-heap, and deletion. Most aspirants can recite that build-heap runs in O(n) time; far fewer can derive it, and the derivation is what the theory variants test. This post builds the heap up from its array representation, derives the O(n) bound properly, and then solves the array-state-after-K-operations drills that GATE keeps returning to.
Binary heap basics: a complete tree living in an array
A binary heap is a complete binary tree that satisfies the heap property. In a max-heap every node's key is at least the keys of its children, so the maximum sits at the root; a min-heap flips the inequality and holds the minimum there. Completeness means every level is full except possibly the last, which fills strictly left to right.
Completeness lets the tree live in a plain array with no pointers. With 1-based indexing, node i has its parent at floor(i/2) and its children at 2i and 2i + 1; the 0-based scheme shifts these to floor((i - 1)/2), 2i + 1 and 2i + 2. GATE solutions conventionally use 1-based indexing, but check which convention the question states before computing an index.
One structural fact answers a whole family of questions: in an n-element heap, the leaves occupy indices floor(n/2) + 1 through n, roughly half the array. So the largest element of a min-heap must be one of those leaves, and finding it means scanning about n/2 candidates, which is Theta(n), not O(log n).
![A 7-element array [20, 12, 15, 3, 8, 6, 10] drawn twice: once as boxes with indices 1 to 7, once as the corresponding complete binary tree, with arrows showing index 2 mapping to the left child of index 1 and index 5 mapping to the right child of index 2.](https://kgai.blob.core.windows.net/blog-assets/blog_asset_1784038566946_pf0nhu.jpg)
Heapify (sift-down): the workhorse procedure
Heapify repairs a single violation: the subtrees below node i are already valid max-heaps, but the key at i may be too small. Max-heapify fixes it:
Compare the key at i with its children (where they exist).
If a child is bigger, swap the key with the larger of the two children.
Repeat where the key lands, until it beats both children or becomes a leaf.
The key sinks at most to the bottom, so the cost is proportional to the height of the node it starts at; from the root that is O(log n). The Heap learn module in GATE Guidance by Sanchit Sir teaches the procedure with worked visuals and PYQ practice attached.
Why build-heap is O(n): the derivation done properly
Build-heap converts an arbitrary array into a heap by calling heapify on every internal node, from index floor(n/2) down to 1. The lazy analysis says: about n/2 calls, each O(log n), so O(n log n). True, but not tight.
The tight argument counts by height. A heap on n elements has at most ceil(n/2^(h+1)) nodes at height h, with leaves at height 0. A heapify call started at height h costs at most c times h. Summing c times h times ceil(n/2^(h+1)) gives a main term bounded by (c times n/2) times the sum of h/2^h, plus an O(log-squared n) boundary term from the ceilings. That boundary term is also O(n).
Now the series. The sum of h times x^h for h from 0 to infinity equals x/(1 - x) squared, which at x = 1/2 evaluates to exactly 2. Substituting back, the main term is at most (c times n/2) times 2, which is c times n. The boundary term does not change the asymptotic result. Build-heap is O(n), and since it must at least read every element, it is Theta(n).
The contrast to memorise: inserting one element at a time is Theta(n log n) worst case, since late insertions can each climb the full height; in build-heap, expensive nodes are exponentially rare, so the total stays linear.
Build-heap worked numerical: watch the array change
Take A = [10, 8, 15, 3, 12, 6, 20], n = 7, 1-based, and build a max-heap. Internal nodes are indices 3, 2, 1, processed in that order.
i = 3 (key 15, children 6 and 20): larger child is 20, swap. Array: [10, 8, 20, 3, 12, 6, 15]. The moved key 15 is now a leaf, stop.
i = 2 (key 8, children 3 and 12): larger child is 12, swap. Array: [10, 12, 20, 3, 8, 6, 15]. Key 8 is a leaf, stop.
i = 1 (key 10, children 12 and 20): larger child is 20, swap. Array: [20, 12, 10, 3, 8, 6, 15]. Key 10 now sits at index 3 with children 6 and 15; larger is 15, swap. Array: [20, 12, 15, 3, 8, 6, 10]. Leaf, stop.
Final heap: [20, 12, 15, 3, 8, 6, 10], built in exactly 4 swaps. GATE asks this shape both ways: state the final array, or count the swaps or comparisons.
Deletion from a max-heap: the array after K operations
Delete-max (extract-max) has fixed steps:
Save the root (the maximum).
Move the last element of the heap into the root position and shrink the heap by one.
Sift the new root down with max-heapify.
Drill it on the heap we just built: [20, 12, 15, 3, 8, 6, 10], n = 7.
First deletion. Remove 20, move 10 to the root, n = 6: [10, 12, 15, 3, 8, 6]. Heapify: the root's children are 12 and 15, larger is 15, swap, giving [15, 12, 10, 3, 8, 6]. Key 10 now has one child, 6, and wins, stop.
Second deletion. Remove 15, move 6 to the root, n = 5: [6, 12, 10, 3, 8]. Children of the root are 12 and 10, larger is 12, swap: [12, 6, 10, 3, 8]. Key 6 has children 3 and 8, larger is 8, swap: [12, 8, 10, 3, 6]. The array after two deletions is [12, 8, 10, 3, 6].
Insertion is the mirror image: place the new key at index n + 1 and sift it up, swapping while the parent is smaller. Inserting 14 appends it at index 6; it swaps past 10 and 12 to give [14, 8, 12, 3, 6, 10].
Heap facts and question shapes GATE tests again and again
The complexity table below is pure teaching content. Learn it cold.
Operation on an n-element binary heap | Worst-case cost |
|---|---|
Find max (max-heap) | O(1) |
Insert (sift-up) | O(log n) |
Delete max (sift-down) | O(log n) |
Build-heap from an array | Theta(n) |
Find min in a max-heap | Theta(n) |
Search for an arbitrary key | Theta(n) |
Heap questions keep landing in five shapes: For cycle-specific paper rules and scoring, use the official GATE portal.
Array state after K operations. Exactly the drills above: build, then delete or insert a few times, and pick the resulting array among four close options. A misread index convention flips the answer.
Build-heap on a given array. Final array, number of swaps, or number of comparisons.
Complexity assertions. Build-heap being Theta(n) is the favourite trap, because O(n log n) feels safer to the unsure; the derivation above lets you pick the tight bound with confidence.
Position reasoning. The largest element of a min-heap lies at a leaf. The second smallest element of a min-heap with distinct keys is a child of the root. Locating the kth smallest takes k extract-mins, costing O(k log n).
NAT counting. Swap and comparison counts appear as numerical-answer questions with no options to lean on. Our breakdown of MCQ, MSQ and NAT question types in GATE covers the execution discipline each format needs.
The next step: drill heaps until the procedure is boring
Heaps reward exactly one thing: error-free execution of a fixed procedure under time pressure. Read the derivation once until the height argument feels obvious, then move entirely to solving.
Work the topic on the Heap learn module linked above, then test yourself under exam conditions. The GATE Test Series carries 39 subject-wise grand tests, three of them on Data Structures, plus 7 full-length mocks, with rank lists and per-topic analysis that show whether heap questions are costing you marks. For the rest of the paper, the GATE category page maps the full course line-up.
Derive build-heap once, hand-solve one build and two deletions, and memorise the complexity table. Do that and every heap question becomes a two-minute procedure, not a puzzle.
