Question

Chegg Suppose the heap is a full tree, size 2^n-1. what is the minimum number of steps to change a min heap to a max heap. Show your logic.

Answer 1

Step-by-step explanation:

We start from the bottom-most and rightmost internal node of min Heap and then heapify all internal modes in the bottom-up way to build the Max heap.

To build a heap, the following algorithm is implemented for any input array.

BUILD-HEAP(A)

heapsize := size(A)

for i := floor(heapsize/2) downto 1

do HEAPIFY(A, i)

end for

Convert the given array of elements into an almost complete binary tree.

Ensure that the tree is a max heap.

Check that every non-leaf node contains a greater or equal value element than its child nodes.

If there exists any node that does not satisfy the ordering property of max heap, swap the elements.

Start checking from a non-leaf node with the highest index (bottom to top and right to left).