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

~120s

Extract-max on a heap

A max-heap is stored as [50, 30, 40, 10, 20, 35]. One extract-max operation is performed. What is the resulting array?

Show the answer and the worked solution

Correct answer: D.

40, 30, 35, 10, 20

Worked solution

  1. The maximum 50 is removed and the last element, 35, is moved to the root, leaving the five-element array [35, 30, 40, 10, 20].
  2. Sift 35 down: its children are 30 at index 1 and 40 at index 2, and the larger is 40.
  3. Since 40 > 35 the two swap, giving [40, 30, 35, 10, 20].
  4. Index 2 has no children in a five-element array, so sifting stops and the heap property holds.

Answer: 40, 30, 35, 10, 20.

The idea

Extract-max is always the same three moves: take the root, promote the last leaf, sift down against the larger child. Swapping with the smaller child would break the heap immediately.

Shortcut. After 50 goes, the new root must be the larger child 40, which rules out 35 at the top; 35 then lands at index 2, a leaf, and 30, 10 and 20 never move.

Common trap. "35, 30, 40, 10, 20" moves the last leaf to the root and stops, skipping the sift-down against the larger child 40.

Data Structures & Algorithms

22 of 40

Level

Hard

Target time

~120s

PreviousNext
AI InterviewGet started

Extract-max on a heap — Aptitude Question

Extract-max on a heap: A max-heap is stored as [50, 30, 40, 10, 20, 35]. One extract-max operation is performed. Answer and worked solution on CodeKairo.

Question

A max-heap is stored as [50, 30, 40, 10, 20, 35]. One extract-max operation is performed. What is the resulting array?

Options

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

Correct answer: D. 40, 30, 35, 10, 20

Worked solution

  1. The maximum 50 is removed and the last element, 35, is moved to the root, leaving the five-element array [35, 30, 40, 10, 20].
  2. Sift 35 down: its children are 30 at index 1 and 40 at index 2, and the larger is 40.
  3. Since 40 > 35 the two swap, giving [40, 30, 35, 10, 20].
  4. Index 2 has no children in a five-element array, so sifting stops and the heap property holds.

Answer: 40, 30, 35, 10, 20.

The idea

Extract-max is always the same three moves: take the root, promote the last leaf, sift down against the larger child. Swapping with the smaller child would break the heap immediately.

Shortcut. After 50 goes, the new root must be the larger child 40, which rules out 35 at the top; 35 then lands at index 2, a leaf, and 30, 10 and 20 never move.

Common trap. "35, 30, 40, 10, 20" moves the last leaf to the root and stops, skipping the sift-down against the larger child 40.

All Data Structures & Algorithms questions · placement mock tests