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

0 · Recall Warm-up

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

• In an AVL tree, what range of balance factors is allowed? from Lesson 4.6
• In a BST, where is the maximum key? from Lesson 4.5.1
• In a 0-based array layout of a binary tree, what are the children of index i? from Lesson 4.2.3

1 · The Hook

🎣

In a hospital emergency room, patients are not treated in arrival order but by urgency: the most critical patient is always next. Lesson 3.3.3 called this a priority queue. Keeping the patients fully sorted would be wasted effort — we only ever need the top one. A heap keeps just enough order to have the maximum at the front, and lives in a plain array.

2 · Predict First

🤔

If every parent is larger than its children, where in the tree is the largest key? Where could the smallest key be? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

The largest is at the root (every path from it goes downward in value). The smallest has no smaller child, so it is a leaf — but it can be any leaf.

Two rules

A binary heap is a binary tree that satisfies:

• Shape: it is a complete binary tree (all levels full except possibly the last, which is filled from the left).
• Order (heap property): in a max-heap every parent ≥ its children; in a min-heap every parent ≤ its children.

Unlike a BST, there is no left–right ordering between siblings or cousins.

Array storage

Because the tree is complete, it is stored level by level in an array with no gaps (Lesson 4.2.3):

A heap with n keys has height ⌊log₂ n⌋.

Checking an array

An array is a max-heap iff every element is ≤ its parent: one comparison per non-root element, O(n).

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, 12, 16, 13, 10, 8, 14};
    printf("%d %d\n", isMaxHeap(p, 7), isMaxHeap(q, 7));
    return 0;
}

Output

1 0

In q, 12 at index 1 has the child 13 at index 3, which is larger: not a heap.

What a heap gives

4 · Visual

Max-heap 100 80 90 50 60 70 40 30 20: the tree and the same keys in the array (0-based indices). Leaves are indices 4…8.

index:   0    1    2    3    4    5    6    7    8
key:   100   80   90   50   60   70   40   30   20

                 100 [0]
              /        \
          80 [1]       90 [2]
          /   \        /   \
      50 [3] 60 [4] 70 [5] 40 [6]
       /  \
   30 [7] 20 [8]

children of 1: 2*1+1 = 3, 2*1+2 = 4      parent of 8: (8-1)/2 = 3

The array is the level order of a complete tree; index arithmetic replaces pointers.

5 · Worked Examples

Example 1 Easy

In the heap above, what are the parent of index 6 and the children of index 3? Which indices are leaves?

Solution

Parent of 6: ⌊5/2⌋ = 2 (key 90). Children of 3: 7 and 8 (keys 30, 20). Leaves: indices ⌊9/2⌋ = 4 to 8.

Example 2 Medium

Is 89 19 50 17 12 15 2 5 7 11 6 9 100 a max-heap?

Solution

No. 100 at index 12 has parent ⌊11/2⌋ = 5 (key 15) and 100 > 15. Checker: false.

Example 3 GATE

A max-heap has n = 1000 distinct keys. In which index range must the minimum key lie (0-based)? How many keys must be examined to find it?

Solution

The minimum is a leaf: indices ⌊1000/2⌋ = 500 to 999, i.e. 500 keys (499 comparisons). Finding the minimum is O(n), not O(log n).

6 · GATE Traps

⚠️

• A heap is complete: no gaps in the array; a non-complete tree is never a heap.
• Heap order is only parent–child; siblings are unordered, and inorder is not sorted.
• Check which indexing (0-based or 1-based) the question uses before applying formulas.
• Minimum of a max-heap: any leaf; search is O(n).
• A sorted (descending) array is always a max-heap, but most heaps are not sorted.

8 · Memory Hook

🧠

“Boss above, no gaps.” Every parent beats its children (order), and the tree is filled left to right (shape).

9 · Connect the Dots

Lesson 5.1 defined a heap and its array layout. A static heap is not useful: patients arrive and leave. Next lesson answers: how do we add a key or remove the maximum while keeping both heap rules, in O(log n)?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markShape

Which must a binary heap be?

• (A) a complete binary tree
• (B) an AVL tree with sorted inorder
• (C) a BST
• (D) a perfect binary tree

Q2NAT1 markIndex

In a 0-based max-heap array, what is the index of the parent of index 13?

Numerical answer: ________

Q3MCQ2 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, 12, 16, 13, 10, 8, 14};
    printf("%d %d\n", isMaxHeap(p, 7), isMaxHeap(q, 7));
    return 0;
}

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

Q4MSQ1 markCosts

For a max-heap of n keys, which are O(1)?

• (A) finding the minimum
• (B) reading the left child index of i
• (C) searching for a given key
• (D) finding the maximum

Q5NAT2 marksLeaves

A heap has 37 keys. How many of them are leaves?

Numerical answer: ________

11 · Rule Card

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

12 · Concept Ledger

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

binary heapmax-heap / min-heapheap propertyheap array indexing

13 · Answer Vault