Question

The essential part of Heap sort is construction of max-heap. Consider the tree shown below, the node 24 violates the max-heap property. Once heapify procedure is applied to it, which position will it be in?

(a) 4

(b) 5

(c) 8

(d) 9

I got this question in examination.

My doubt stems from Heapsort topic in section Sorting of Data Structures & Algorithms II

Answer 1

Right choice is (d) 9

Explanation: In max-heap element at each node is smaller than or equal to the element at its parent node. On applying the heapify procedure on item at position 2, it will be in position 9 as shown below.