AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumheapinsertion

~105s

Inserting into a min-heap

A min-heap is stored as the array [10, 20, 15, 30, 40]. The key 5 is inserted. What does the array look like afterwards?

Show the answer and the worked solution

Correct answer: B.

5, 20, 10, 30, 40, 15

Worked solution

  1. The key is appended at index 5, giving [10, 20, 15, 30, 40, 5].
  2. Its parent is index (5 − 1) / 2 = 2, holding 15. Since 5 < 15 they swap, giving [10, 20, 5, 30, 40, 15].
  3. The parent of index 2 is index 0, holding 10. Since 5 < 10 they swap, giving [5, 20, 10, 30, 40, 15].
  4. The key is now at the root, so sifting stops.

Answer: 5, 20, 10, 30, 40, 15.

The idea

Sifting up touches only the path from the new leaf to the root, so insertion costs O(log n). Note that a heap is only partially ordered — the array is not, and need not be, sorted.

Shortcut. 5 sifts up along its own path only, index 5 → 2 → 0, so 20, 30 and 40 never move, and the displaced 15 and 10 each drop one level.

Common trap. "5, 20, 15, 30, 40, 10" swaps the new key straight with the root, skipping its parent 15 on the way up.

Data Structures & Algorithms

20 of 40

Level

Medium

Target time

~105s

PreviousNext
AI InterviewGet started

Inserting into a min-heap — Aptitude Question

Inserting into a min-heap: A min-heap is stored as the array [10, 20, 15, 30, 40]. The key 5 is inserted. Answer and worked solution on CodeKairo.

Question

A min-heap is stored as the array [10, 20, 15, 30, 40]. The key 5 is inserted. What does the array look like afterwards?

Options

  1. 5, 10, 20, 30, 40, 15
  2. 5, 20, 10, 30, 40, 15
  3. 5, 20, 15, 30, 40, 10
  4. 10, 20, 15, 30, 40, 5
Show the answer and the worked solution

Correct answer: B. 5, 20, 10, 30, 40, 15

Worked solution

  1. The key is appended at index 5, giving [10, 20, 15, 30, 40, 5].
  2. Its parent is index (5 − 1) / 2 = 2, holding 15. Since 5 < 15 they swap, giving [10, 20, 5, 30, 40, 15].
  3. The parent of index 2 is index 0, holding 10. Since 5 < 10 they swap, giving [5, 20, 10, 30, 40, 15].
  4. The key is now at the root, so sifting stops.

Answer: 5, 20, 10, 30, 40, 15.

The idea

Sifting up touches only the path from the new leaf to the root, so insertion costs O(log n). Note that a heap is only partially ordered — the array is not, and need not be, sorted.

Shortcut. 5 sifts up along its own path only, index 5 → 2 → 0, so 20, 30 and 40 never move, and the displaced 15 and 10 each drop one level.

Common trap. "5, 20, 15, 30, 40, 10" swaps the new key straight with the root, skipping its parent 15 on the way up.

All Data Structures & Algorithms questions · placement mock tests