Heap GATE drills: k-th largest, number of heaps, comparisons, d-ary heaps

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What does bottom-up build-heap cost? from Lesson 5.3
• In a 0-based heap of n keys, which indices are leaves? from Lesson 5.1
• How many binary tree shapes have n nodes? from Lesson 4.3.3

1 · The Hook

🎣

Heap questions in GATE are rarely “perform this insertion”; they ask where something can be, how many heaps exist, or what changes with three children per node. Each has a short method.

2 · Predict First

🤔

How many different max-heaps can be formed from the keys 1, 2, 3, 4, 5? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

8. 5 is the root; the shape has 3 keys on the left and 1 on the right. Choose which 3 of the remaining 4 keys go left (C(4, 3) = 4), the left part can be arranged in 2 heaps, the right in 1: 4 × 2 × 1 = 8.

Where can the k-th largest be?

In a max-heap with distinct keys, the k-th largest has at most k − 1 larger keys, and all its ancestors are larger, so its depth is ≤ k − 1. The 2nd largest is a child of the root (index 1 or 2); the 3rd largest is at depth 1 or 2 (indices 1 … 6). Finding the k-th largest: delete the maximum k times, O(k log n). The minimum is a leaf (O(n) to find).

int main(void)
{
    int h[] = {100, 80, 90, 50, 60, 70, 40, 30, 20}, n = 9, i, min = h[n / 2];
    for (i = n / 2 + 1; i < n; i++)          /* only the leaves can hold the minimum */
        if (h[i] < min) min = h[i];
    printf("%d %d\n", min, n - n / 2);
    return 0;
}

Output

20 5

Number of heaps on n distinct keys

The shape is fixed (complete tree). The maximum is the root; choose which L of the other n − 1 keys go to the left subtree (L is fixed by the shape), and recurse:

H(n) = C(n − 1, L) × H(L) × H(n − 1 − L)

Costs and comparison counts

d-ary heaps

A d-ary heap gives each node up to d children (a ternary heap has d = 3). 0-based: children of i are d·i + 1 … d·i + d, parent ⌊(i − 1)/d⌋. Height ≈ log_d n, so insertion is cheaper (≈ log_d n comparisons) but deletion compares d children per level (≈ d·log_d n).

4 · Visual

Drawn as a binary heap for indexing only — read as a ternary (3-ary) max-heap, index 0 has children 1, 2, 3 and index 1 has children 4, 5, 6.

ternary max-heap 9 5 6 8 3 1   (children of i: 3i+1, 3i+2, 3i+3)

              9 [0]
         /     |      \
      5 [1]  6 [2]   8 [3]
      /  \
   3 [4] 1 [5]

insert 7:  index 6, parent (6-1)/3 = 1 (5): swap -> 9 7 6 8 3 1 5
insert 2:  index 7, parent 2 (6): stays       -> 9 7 6 8 3 1 5 2
insert 10: index 8, parent 2 (6): swap; then parent 0 (9): swap
                                              -> 10 7 9 8 3 1 5 2 6

Same rules as a binary heap, with d-way index arithmetic.

5 · Worked Examples

Example 1 Easy

A max-heap of distinct keys has 15 keys. List the indices where the 3rd largest key can be.

Solution

Depth 1 or 2: indices 1 to 6. (It can be a child of the root, or a child of the 2nd largest.)

Example 2 Medium

How many distinct max-heaps can be built from 7 distinct keys?

Solution

Shape: perfect tree, 3 keys on each side. C(6, 3) × H(3) × H(3) = 20 × 2 × 2 = 80.

Example 3 GATE

A 3-ary max-heap is stored in an array (0-based). Which of these is a valid 3-ary max-heap: 9 5 6 8 3 1 / 9 3 6 8 5 1 / 9 6 3 1 8 5 / 9 1 6 8 3 5? After inserting 7, 2, 10 in that order into the valid one, what is the array?

Solution

Only 9 5 6 8 3 1 (index 1’s children are indices 4, 5, 6). After the insertions: 10 7 9 8 3 1 5 2 6 (see the visual).

6 · GATE Traps

⚠️

• The k-th largest is at depth ≤ k − 1, not at index k − 1.
• Number of heaps uses the fixed shape: L is determined by n, not chosen.
• In a d-ary heap the parent formula is ⌊(i − 1)/d⌋ (0-based).
• Deletion in a d-ary heap compares d children per level.
• Find-min in a max-heap is O(n); heaps do not support fast search.

8 · Memory Hook

🧠

“Rank k lives within k − 1 steps of the top; count heaps by choosing the left team.”

9 · Connect the Dots

Phase 5 is complete: heaps give the best item in O(1) and repair themselves in O(log n). Trees and heaps are hierarchies: each item has one parent. Road maps, social networks and prerequisites have no single top and may contain cycles. Phase 6 answers: how are such networks stored and explored?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksCount

How many distinct max-heaps can be built from 6 distinct keys?

Numerical answer: ________

Q2MCQ1 markSecond largest

In a 0-based max-heap of distinct keys, the second largest key can be at:

• (A) any index ≥ 1
• (B) index n − 1
• (C) index 3 or 4
• (D) index 1 or 2 only

Q3MCQ2 marksTernary

In a 0-based ternary heap, the parent of index 10 is:

• (A) 5
• (B) 2
• (C) 4
• (D) 3

Q4MCQ2 marksOutput

What does this print?

int main(void)
{
    int h[] = {100, 80, 90, 50, 60, 70, 40, 30, 20}, n = 9, i, min = h[n / 2];
    for (i = n / 2 + 1; i < n; i++)          /* only the leaves can hold the minimum */
        if (h[i] < min) min = h[i];
    printf("%d %d\n", min, n - n / 2);
    return 0;
}

• (A) 30 4
• (B) 20 5
• (C) 20 4
• (D) 40 5

Q5MSQ2 marksCosts

For a binary max-heap of n keys, which are Θ(n) in the worst case?

• (A) searching for an arbitrary key
• (B) build-heap
• (C) deleting the maximum
• (D) finding the minimum

11 · Rule Card

• k-th largest (distinct keys) at depth ≤ k − 1; 2nd largest at index 1 or 2; k-th found in O(k log n).
• H(n) = C(n − 1, L)·H(L)·H(n − 1 − L): 1, 1, 2, 3, 8, 20, 80.
• Insert ≤ h, delete ≤ 2h comparisons; find-min O(n).
• d-ary (0-based): children d·i + 1 … d·i + d; parent ⌊(i − 1)/d⌋; height ≈ log_d n.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

k-th largest positionnumber of heaps H(n)heap comparison countsd-ary heap

13 · Answer Vault