Spotting a valid max-heap — Aptitude Question
Spotting a valid max-heap: Reading each array as a complete binary tree in which the children of index i sit at 2i… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 105 seconds
Question
Reading each array as a complete binary tree in which the children of index i sit at 2i + 1 and 2i + 2, which array satisfies the max-heap property?
Options
- [8, 9, 7, 3, 2, 1]
- [9, 7, 8, 3, 2, 5]
- [9, 8, 7, 6, 5, 10]
- [10, 5, 9, 2, 6, 3]
Show the answer and the worked solution
Correct answer: B. [9, 7, 8, 3, 2, 5]
Worked solution
- In
[8, 9, 7, 3, 2, 1]the root 8 is smaller than its child 9, so it fails. - In
[9, 8, 7, 6, 5, 10]index 2 holds 7 while its child at index 5 holds 10, so it fails. - In
[10, 5, 9, 2, 6, 3]index 1 holds 5 while its child at index 4 holds 6, so it fails. - In
[9, 7, 8, 3, 2, 5]the root 9 dominates 7 and 8, index 1 dominates 3 and 2, and index 2 dominates 5, so every parent is at least as large as its children.
Answer: [9, 7, 8, 3, 2, 5].
The idea
A heap constrains parents against children and nothing else, so a valid heap can look thoroughly unsorted. Checking the ⌊n/2⌋ parents is enough — leaves are trivially fine.
Shortcut. Check the last parent first: in six elements index 2 has one child, index 5, and 7 < 10 kills [9, 8, 7, 6, 5, 10]; the root kills [8, 9, …] and 5 < 6 kills [10, 5, 9, 2, 6, 3].
Common trap. "[9, 8, 7, 6, 5, 10]" is almost descending and looks heap-like, but 10 sits at index 5 as a child of 7.
All Data Structures & Algorithms questions · placement mock tests