heapsort

heapsort.js

// 0 based index
var iParent = (i) => Math.floor((i-1)/2);
var iLeftChild = (i) => 2*i + 1;
var iRightChild = (i) => 2*i + 2;

function heapsort(list, count) {
  // first build a heap
  maxHeapify(list, count);
  
  // remove root and decrease range of list when fixing it
  var start = 0;
  var end = count - 1;
  while (end > start) {
    swap(list, start, end);
    end = end - 1;
    siftDown(list, start, end);
  }
}

// create max heap structure
function maxHeapify(list, count) {
  // start from the parent of the last node and go up
  var start = iParent(count - 1);
  
  // fix all nodes until after reaching the root node (at index 0);
  while (start >= 0) {
    siftDown(list, start, count - 1);  
    start = start - 1;
  }
}

// fix heap
function siftDown(list, start, end) {
  var root = start;
  var iSwap;
  var child;
  
  while (iLeftChild(root) <= end) {
    child = iLeftChild(root);
    iSwap = root;
    
    // check left child value
    if (list[iSwap] < list[child]) {
      iSwap = child;
    }
    // check right child value (if any)
    if (child + 1 <= end && list[iSwap] < list[child + 1]) {
      iSwap = child + 1;
    }
    // if root is the largest value we are done
    if (root === iSwap) {
      return;
    } else {
      // swap with greatest value child and proceed with swapped root index
      swap(list, root, iSwap);
      root = iSwap;
    }
  }
}

// swap function
function swap(list, a, b) {
  var temp = list[a];
  list[a] = list[b];
  list[b] = temp;
}

// example
var list = [4,2,8,99,11,6,33];
heapsort(list, list.length);