In C++, the following functions will be used to implement Heap Sort.
- heapify(Array, size, index)
- heapSort(Array, size)
The heapify function will convert all non-leaf nodes of the heap to Max-Heap and heapSort will first create a priority queue, and then repeatedly pop the elements from the heap until it becomes empty.
Implementation of HeapSort has been provided below:
xxxxxxxxxx42
console.log(heapSort([4, 11, 1, 21, 34, 85, 6, 49, 7, 12, 31]));const heapSort = function(arr) { const n = arr.length; for (let i = Math.floor(n/2) - 1; i >= 0; i--) { heapify(arr, n, i); }​ for (let i = n - 1; i >= 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); }​ return arr;}​const heapify = function(arr, n, i) { // find places in array heap let left = 2 * i + 1; let right = 2 * i + 2;​ if (left >= n && right >= n) { return; }​ const leftValue = (left >= n) ? Number.NEGATIVE_INFINITY : arr[left]; const rightValue = (right >= n) ? Number.NEGATIVE_INFINITY : arr[right];​ if (arr[i] > leftValue && arr[i] > rightValue) { return; }​ if (leftValue > rightValue) { swap(arr, i, left); heapify(arr, n, left);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
