Heap insert and delete

ACompressed recap

🧾

Insert puts the key in the next free index and sifts it up (swap with the parent while larger): ≤ h comparisons. Deleting the root moves the last key to the root and sifts it down (swap with the larger child while smaller): ≤ 2h comparisons. Both O(log n); changing a key uses sift-up or sift-down accordingly.

BMerged rule card

5.2 Heap insertion (sift-up) and deleting the root (sift-down)

• Insert: place at index n; sift-up (swap with parent while larger); ≤ h comparisons.
• Delete max: root ← last; n−−; sift-down (swap with larger child while smaller); ≤ 2h comparisons.
• Both O(log n).
• Increase key → sift-up; decrease key → sift-down (max-heap).

CInterleaved GATE-style questions

Q1MCQ2 marksInsert

Insert 10, 20, 15, 30, 40 one by one into an empty max-heap. Final array:

• (A) 40 30 15 20 10
• (B) 40 20 30 10 15
• (C) 40 30 20 15 10
• (D) 40 30 15 10 20

Q2NAT1 markComparisons

Maximum comparisons to delete the root of a max-heap of height 5?

Numerical answer: ________

Q3MCQ1 markSift-down

In a min-heap, sift-down swaps the moved key with:

• (A) its larger child
• (B) its parent
• (C) the last element
• (D) its smaller child

Q4MCQ2 marksOutput

What is the last line printed?

int h[20], n = 0;                       /* max-heap in h[0..n-1] */

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void insert(int x)                       /* sift-up */
{
    int i = n++;
    h[i] = x;
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i)
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) return;
        swap(&h[i], &h[big]);
        i = big;
    }
}

int deleteMax(void)
{
    int top = h[0];
    h[0] = h[--n];                       /* last element to the root */
    siftDown(0);
    return top;
}

void show(void) { int i; for (i = 0; i < n; i++) printf("%d ", h[i]); printf("\n"); }

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, i;
    for (i = 0; i < 7; i++) insert(a[i]);
    show();
    printf("removed %d\n", deleteMax());
    show();
    return 0;
}

• (A) 80 50 70 40 45 35
• (B) 70 45 50 40 35
• (C) 80 45 70 40 50 35
• (D) 80 70 50 40 45 35

Q5NAT2 marksDelete

Delete the maximum from the max-heap 25 15 16 14 10 8 12 13. What key is at index 2 afterwards?

Numerical answer: ________

Q6MSQ1 markCosts

Which are O(log n) in a heap of n keys?

• (A) insert
• (B) search for a key
• (C) delete the root
• (D) increase a key at a known index

Q7NAT2 marksSwaps

Into the max-heap 50 30 40 10 20 the key 45 is inserted. How many swaps occur?

Numerical answer: ________

Q8MCQ1 markWhere

A newly inserted key in a heap of n keys starts at 0-based index:

• (A) n
• (B) n − 1
• (C) 0
• (D) ⌊n/2⌋

DAnswer Vault