The heap idea

ACompressed recap

🧾

A binary heap is a complete binary tree with heap order: in a max-heap every parent ≥ its children (min-heap: ≤). It is stored level by level in an array: 0-based children 2i + 1, 2i + 2 and parent ⌊(i − 1)/2⌋ (1-based: 2i, 2i + 1, ⌊i/2⌋). The maximum is the root; the minimum is one of the n − ⌊n/2⌋ leaves; height ⌊log₂ n⌋.

BMerged rule card

5.1 The heap idea: a complete binary tree in an array; max-heap and min-heap

• Heap = complete binary tree + heap order (max: parent ≥ children; min: parent ≤ children).
• 0-based: children 2i + 1, 2i + 2; parent ⌊(i − 1)/2⌋. 1-based: 2i, 2i + 1; ⌊i/2⌋.
• Leaves: last n − ⌊n/2⌋ positions; height ⌊log₂ n⌋.
• Max at root O(1); min among leaves O(n); search O(n).

CInterleaved GATE-style questions

Q1MCQ1 markValidity

Which array is a max-heap?

• (A) 50 30 40 10 20 35
• (B) 50 40 30 45 20 10
• (C) 50 30 40 35 20 10
• (D) 30 50 40 10 20 35

Q2NAT1 mark1-based

In a 1-based heap array, what is the index of the right child of index 9?

Numerical answer: ________

Q3NAT1 markHeight

Height (edges) of a heap with 100 keys?

Numerical answer: ________

Q4MCQ1 markMinimum

In a max-heap with distinct keys, the minimum key is:

• (A) at some leaf
• (B) always at the last index
• (C) at index n/2
• (D) a child of the root

Q5MSQ2 marksFacts

Which are true?

• (A) Every array sorted in decreasing order is a max-heap.
• (B) A min-heap’s root is its minimum.
• (C) Every max-heap is sorted in decreasing order.
• (D) Siblings in a heap may be in any order.

Q6NAT2 marksLeaves

In a 0-based heap of 20 keys, what is the smallest index of a leaf?

Numerical answer: ________

Q7MCQ1 markSecond largest

In a max-heap of distinct keys (n ≥ 3), the second largest key is at:

• (A) index 3
• (B) index n − 1
• (C) index 1 or 2
• (D) any leaf

Q8MCQ2 marksOutput

What does this print?

int isMaxHeap(int a[], int n)
{
    int i;
    for (i = 1; i < n; i++)
        if (a[(i - 1) / 2] < a[i]) return 0;
    return 1;
}

int main(void)
{
    int p[] = {25, 14, 16, 13, 10, 8, 12};
    int q[] = {25, 14, 16, 13, 10, 18, 12};
    printf("%d %d\n", isMaxHeap(p, 7), isMaxHeap(q, 7));
    return 0;
}

• (A) 0 0
• (B) 1 0
• (C) 1 1
• (D) 0 1

DAnswer Vault