A 3-ary max heap is like a binary max heap, but each node can have up to 3…
2006
A 3-ary max heap is like a binary max heap, but each node can have up to 3 children. In a 0-based array representation, the root is stored at a[0], the next level is stored from a[1] to a[3], and the following level starts from a[4].
The current valid 3-ary max heap is [9, 5, 6, 8, 3, 1]. An item x is inserted by placing it at a[n] and pushing it up until the max-heap property is satisfied.
Suppose the elements 7, 2, 10 and 4 are inserted in that order. Which sequence represents the resultant heap array?
- A.
10, 7, 9, 8, 3, 1, 5, 2, 6, 4
- B.
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
- C.
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
- D.
10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Attempted by 121 students.
Show answer & explanation
Correct answer: A
Parent formula: For 0-based indexing in a 3-ary heap, parent(i) = floor((i - 1) / 3).
Starting heap: [9, 5, 6, 8, 3, 1].
Insert 7: place at index 6. Its parent is 5, so swap. Heap becomes [9, 7, 6, 8, 3, 1, 5].
Insert 2: place at index 7. Its parent is 6, so no swap. Heap becomes [9, 7, 6, 8, 3, 1, 5, 2].
Insert 10: place at index 8. Swap with 6, then swap with 9. Heap becomes [10, 7, 9, 8, 3, 1, 5, 2, 6].
Insert 4: place at index 9. Its parent is 9, so no swap.
Final answer: [10, 7, 9, 8, 3, 1, 5, 2, 6, 4], which matches option A.