implement a heap sort and demonstrate its functionality Solution PSEUDOCODE is a
ID: 3657697 • Letter: I
Question
implement a heap sort and demonstrate its functionalityExplanation / Answer
PSEUDOCODE is as follows: function heapSort(a, count) is input: an unordered array a of length count (first place a in max-heap order) heapify(a, count) end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2 while end > 0 do (swap the root(maximum value) of the heap with the last element of the heap) swap(a[end], a[0]) (decrease the size of the heap by one so that the previous max value will stay in its proper placement) end := end - 1 (put the heap back in max-heap order) siftDown(a, 0, end) function heapify(a, count) is (start is assigned the index in a of the last parent node) start := (count - 2) / 2 while start = 0 do (sift down the node at index start to the proper place such that all nodes below the start index are in heap order) siftDown(a, start, count-1) start := start - 1 (after sifting down the root all nodes/elements are in heap order) function siftDown(a, start, end) is input: end represents the limit of how far down the heap to sift. root := start while root * 2 + 1 = end do (While the root has at least one child) child := root * 2 + 1 (root*2 + 1 points to the left child) swap := root (keeps track of child to swap with) (check if root is smaller than left child) if a[swap]Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.