Heap drills

ACompressed recap

🧾

The k-th largest key of a max-heap (distinct keys) lies at depth ≤ k − 1; the minimum is a leaf. The number of heaps is H(n) = C(n − 1, L)·H(L)·H(R) with L fixed by the shape (1, 1, 2, 3, 8, 20, 80). Insertion needs ≤ h comparisons, deletion ≤ 2h. A d-ary heap has children d·i + 1 … d·i + d and parent ⌊(i − 1)/d⌋.

BMerged rule card

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

• 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.

CInterleaved GATE-style questions

Q1NAT1 markCount

How many distinct max-heaps on 4 distinct keys?

Numerical answer: ________

Q2NAT2 marksPositions

In a 0-based max-heap of 31 distinct keys, how many different indices can hold the 3rd largest key?

Numerical answer: ________

Q3MCQ2 marksTernary

Which is a valid 0-based ternary max-heap?

• (A) 9 6 3 1 8 5
• (B) 9 3 6 8 5 1
• (C) 9 5 6 8 3 1
• (D) 9 1 6 8 3 5

Q4MCQ1 markk-th

The k-th largest of a max-heap (k small) can be found in:

• (A) O(log k)
• (B) O(n log n) only
• (C) O(k log n)
• (D) O(1)

Q5NAT2 marksTernary insert

Insert 7, 2, 10 (in that order) into the ternary max-heap 9 5 6 8 3 1. Which key is at index 2 at the end?

Numerical answer: ________

Q6MSQ1 markd-ary

For a d-ary heap with n keys (d ≥ 2), which are true?

• (A) Its height is about log_d n.
• (B) Deleting the root compares up to d children per level.
• (C) It need not be complete.
• (D) Insertion is cheaper than in a binary heap for large d.

Q7NAT1 markCount

How many distinct max-heaps on 5 distinct keys?

Numerical answer: ________

Q8MCQ2 marksOutput

What does this print?

int main(void)
{
    int h[] = {100, 80, 90, 50, 60, 70, 40, 30, 55}, 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) 55 5
• (B) 30 5
• (C) 20 5
• (D) 30 4

DAnswer Vault