The smallest item in a heap (assume min-heap) must appear in position 0, and the second smallest must be in position 1 or position 2.
(a) (3 points) Give the list of positions in a heap where the third smallest can appear. (b) (3 points) Give a list of positions where the fourth smallest can appear.
(a) List of positions in a heap where the third smallest can appear is 1,2,3,4,5 and 6.
(b) List of positions where the fourth smallest can appear is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and 14.
For example:
In the given graph the deepest level where 3rd smallest element can occur is 3 (element 2).
In the given graph the deepest level where 4th smallest element can occur is 4 (element 3).
So we can see that at maximum the 3rd smallest element require positions atmost upto 3rd level and 4th smallest element require positions atmost upto 4th level.
Get Answers For Free
Most questions answered within 1 hours.