堆排序，首先建立大头堆，然后将根元素与最后一个叶子节点交换（此时不一定符合堆的定义，调整成堆），重复此步骤

heap_sort.js

/**
 * 在数组中按下标交换数据
 * @param {Array} arr 数据源
 * @param {number} prev 需交换的下标之一
 * @param {number} next 需交换的下标之一
 */
function swap(arr, prev, next) {
  var temp = arr[prev];
  arr[prev] = arr[next];
  arr[next] = temp;
}

/**
 * 建堆操作，若父节点下标为i，则左孩子下标为2*i+1，右孩子下标为2*i+2
 * @param {Array} arr 建堆所需的数据源，数组
 * @param {number} index 根节点下标
 * @param {number} size 堆大小
 */
function heapify(arr, index, size) {
  var root;
  var leftChild;
  var rightChild;
  while(index < size) {
    root = index;
    
    leftChild = root * 2 + 1;
    rightChild = root * 2 + 2;
    // 左子节点大于父节点，交换
    if(leftChild < size && arr[leftChild] > arr[root]) {
      root = leftChild;
    }
    // 右子节点大于父节点，交换
    if(rightChild < size && arr[rightChild] > arr[root]) {
      root = rightChild;
    }
    
    if(root === index) {
      return;
    }
    
    swap(arr, index, root);
    
    index = root;
  }
}

/**
 * 构建大头堆
 * @param {Array} arr 数据源
 */
function build_max_heap(arr) {
  var len = arr.length;
  // 为什么从下标Math.floor(arr.length / 2)-1开始呢，因为此后的数据都是叶子节点
  for(var i=Math.floor(arr.length / 2)-1; i>=0; i--) {
    heapify(arr, i, len);
  }
}

/**
 * 堆排序，大头堆根节点（下标为0）为最大值
 * @param {Array} arr 数据源
 * @return {Array} arr 排序之后的数据
 */
function heap_sort(arr) {
  build_max_heap(arr);  // 构建大头堆，此时arr[0]为最大值
  var lastIndex = arr.length - 1;
  while(lastIndex > 0) {
    swap(arr, 0, lastIndex);  // 将大值放在数组后端
    heapify(arr, 0, lastIndex); // 交换后要重新进行建堆操作，此时数组后端已经有序的数据不再参与
    lastIndex -= 1;
  }
  return arr;
}