Analysis of Algorithms: Heapification, Minimum Spanning Tree, Inversions,Sorting, and Random-SelectProblem 1:Answer:The provided solution will not heapify the given array.TheHeapifyHeap()function can beconsidered as building a heap from the bottom up, consecutively pushing downward to establishthe property of the heap.The algorithm for the supporting functionHeapifyHeap()is given below:Algorithmalter_heapify(array, arraySize) isInput:An arrayarrayand its sizearraySize.Ouput:A bubble down array.Assign the index in array of the last parent node to the variablebegin.The index of the lastparent node will be equal to(arraySize-2 ) / 2.//assign valuei← (arraySize-2 ) / 2With the help of awhileloop push down the node at indexbeginto the proper place suchthat all nodes below theindexbeginare in heap order.//create while loopwhile i ≥ 0 do// call PushDown()PushDown(array,begin, arraySize-1)// decrement begini ← i–1After pushing down the root, all the elements will be in heap order. Thus, now the bubble downarray is heapify. An example to show this is as given below:Preview Mode
This document has 8 pages. Sign in to access the full document!