The elements 42,25,30,40,22,35,26 are inserted one by one in the given order…
2018
The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is sorted in an array implementation as
- A.
<42,40,35,25,22,30,26>
- B.
<42,35,40,22,25,30,26>
- C.
<42,40,35,25,22,26,30>
- D.
<42,35,40,22,25,26,30>
Attempted by 292 students.
Show answer & explanation
Correct answer: A
Key idea: maintain the max-heap property (each parent >= its children) after each insertion by bubbling the new element up as needed.
Insert 42 -> <42>
Insert 25 -> <42,25> (25 is a child of 42, no swap)
Insert 30 -> <42,25,30> (30 is a child of 42, no swap)
Insert 40 -> add at end: <42,25,30,40>. 40's parent is 25; since 40 > 25 swap them -> <42,40,30,25>
Insert 22 -> <42,40,30,25,22> (22 is child of 40, no swap)
Insert 35 -> add at end: <42,40,30,25,22,35>. 35's parent is 30; since 35 > 30 swap them -> <42,40,35,25,22,30>. 35's new parent is 42; 35 < 42 so stop.
Insert 26 -> <42,40,35,25,22,30,26>. 26's parent is 35; 26 < 35 so no swap.
Final max-heap array:
<42,40,35,25,22,30,26>
A video solution is available for this question — log in and enroll to watch it.