Representation of a Heap Sort

heapSort.js

const swap = (array, firstItemIndex, lastItemIndex) => {
  const temp = array[firstItemIndex];
  
  array[firstItemIndex] = array[lastItemIndex];
  array[lastItemIndex] = temp;
}

const heapify = (heap, i, max) => {
  let index, leftChild, righChild;
  
  while(i < max) {
    index = i;

    leftChild = 2 * i + 1;
    righChild = leftChild + 1;

    if (leftChild < max && heap[leftChild] > heap[index]) {
      index = leftChild;
    }

    if (righChild < max && heap[righChild] > heap[index]) {
      index = righChild;
    }
      
    if (index == i) {
      return;
    }

    swap(heap,i, index);
    
    i = index;
  }
}

const buildMaxHeap = (array) => {

  let index
  index = Math.floor(array.length / 2 - 1);

  // Build a max heap out of
  // all array elements passed in.
  while (index >= 0) {
    heapify(array, index, array.length);
    index -= 1;
  }
}


const heapSort = (array) => {
  buildMaxHeap(array);

  let lastElement
  lastElement = array.length - 1;

  while(lastElement > 0) {
    swap(array, 0, lastElement);

    heapify(array, 0, lastElement);

    lastElement -= 1
  }
  return array
}

Heap sort

Order: O(nlogn)
Heap sort is a comparison based sorting algorithm based on the heap data structure. It works similar to selection sort by separating data into the sorted and unsorted region but uses a heap data structure instead of a linear time search to find the largest element (the maximum).

Initially, on receiving an unsorted list, the first step in heap sort is to create a Heap data structure(Max-Heap). Once the heap is built, the first element of the Heap is either the largest or smallest(Max-Heap or Min-Heap), so we put the first element of the heap in a new array or mutate the old array by swapping elements around. Then we again make heap using the remaining elements, to again pick the first element of the heap and put it into the array.