AlgoDaily - Merge Sort vs. Quick Sort vs. Heap Sort

Home > Data Structures and Algorithms 🚀 > Pointers and Windows > Merge Sort vs. Quick Sort vs. Heap Sort

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:

xxxxxxxxxx
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);

Programming Categories

Popular Lessons