/** * 从 index 开始检查并保持最大堆性质 * * @array * * @index 检查的起始下标 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax = index, iLeft = 2 * index + 1, iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); maxHeapify(array, iMax, heapSize); // 递归调整 } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }
通常来说，递归主要用在分治法中，而这里并不需要分治。而且递归调用需要压栈/清栈，和迭代相比，性能上有略微的劣势。当然，按照20/80法则，这是可以忽略的。但是如果你觉得用递归会让自己心里过不去的话，也可以用迭代，比如下面这样：
/** * 从 index 开始检查并保持最大堆性质 * * @array * * @index 检查的起始下标 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }
创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：
用 JavaScript 描述如下：
function buildMaxHeap(array, heapSize) { var i, iParent = Math.floor((heapSize - 1) / 2); for (i = iParent; i >= 0; i--) { maxHeapify(array, i, heapSize); } }
堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：
用 JavaScript 描述如下：
function heapSort(array, heapSize) { buildMaxHeap(array, heapSize); for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } }
4.JavaScript 语言实现
最后，把上面的整理为完整的 javascript 代码如下：
function heapSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(array) { var i, iParent = Math.floor(array.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(array, i, array.length); } } function sort(array) { buildMaxHeap(array); for (var i = array.length - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } return array; } return sort(array); }
5.堆排序算法的运用
（1）算法性能/复杂度
堆排序的时间复杂度非常稳定（我们可以看到，对输入数据不敏感），为O(n㏒n)复杂度，最好情况与最坏情况一样。
但是，其空间复杂度依实现不同而不同。上面即讨论了两种常见的复杂度：O(n)与O(1)。本着节约空间的原则，我推荐O(1)复杂度的方法。
（2）算法稳定性
堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。