Heapsort

heap_sort.js

// Assume you sorting an array
// [5,1,2,3] => [1,2,3,5]
// [2,3,5,5,2,0] => [0,2,2,3,5,5]
function _swap(array, index1, index2) {
  var temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

function _buildHeap(array) {
  for (var i = Math.floor(array.length / 2) - 1; i >= 0; i--) {
    _heapify(array, i, array.length);
  }
}

// The point of the heap is to build a tree where the parent node is always
// larger than the left and right node.
function _heapify(array, i, max) {
  var leftIndex = 2 * i + 1,
      rightIndex = 2 * i + 2,
      largestIndex;

  // Compare the left index value with our current index value, to determin which
  // contains the largest index value
  if ((leftIndex < max) && (array[leftIndex] > array[i])) {
    largestIndex = leftIndex;
  } else {
    largestIndex = i;
  }

  // compare the right index value with the largest index value determined by the
  // previous if-else block
  if ((rightIndex < max) && (array[rightIndex] > array[largestIndex])) {
    largestIndex = rightIndex
  }

  if (largestIndex !== i) {
    _swap(array, largestIndex, i);
    _heapify(array, largestIndex, max);
  }
}

// This is a unstable sort. It wont retain the inputted order for equal values.
// e.g. A deck of play cards as the input where it is pre-sort by suite (spade < heart).
// When using heapsort a card with ace of spades might be after a card of aces of heart.
// This is because there is a lot of moving of elements around in building the heap
// and then sort it.
// This algorithm runs in O(n log n) in all cases. You can simiply determine this
// by recongizing the heap is a tree. Breaking down how many times heapify is called
// (n/2 -1) for building the heap and (n - 1) for sorting the heap, the total is
// (3n/2 - 2). And for each case we only recursively traverse the heap with a depth of log n.
function heapSort(array) {
  _buildHeap(array);

  // Walk backwards but only up to the second to last one. due to swapping
  for (var i = array.length - 1; i >= 1; i--) {
    // swap the first and last values, because of the heap property, you know that
    // the very first element is the root node for the heap thus the max value of that subset.
    _swap(array, 0, i);
    // create a subset of the previous heap and to determine the max node value.
    _heapify(array, 0, i);
  }
}