堆排序也是一种很高效的算法，因其把数组当作二叉树来排序而得名。这个算法会根据以下信息，把数组当作二叉树来管理。
1.索引0是树的根节点;
2.除根节点外，任意节点N的父节点是N/2;
3.节点L的左子节点是2*L;
4.节点R的右子节点是2*R+1。
举例来说，可以将数组[3, 5, 1, 6, 4, 7, 2]想象成下面的树:
堆排序算法实现如下:
this.heapSort = function() {
var heapSize = array.length;
buildHeap(array); //{1}
while (heapSize > 1) {
heapSize--;
swap(array, 0, heapSize); //{2}
heapify(array, heapSize, 0); //{3}
}
};
第一步，构造一个满足array[parent(i)] ≥ array[i]的堆结构(行{1})。
第二步，交换堆里第一个元素(数组中较大的值)和最后一个元素的位置(行{2})。这样，最大的值就会出现在它已排序的位置。
第二步可能会丢掉堆的属性。因此，我们还需要执行一个heapify函数，再次将数组转换成 堆，也就是说，它会找到当前堆的根节点(较小的值)，重新放到树的底部。
buildHeap函数实现如下:
var buildHeap = function(array){
var heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 0; i--) {
heapify(array, heapSize, i);
}
};
如果对数组[3, 5, 1, 6, 4, 7, 2]调用buildHeap函数，堆的构建过程如下:
最后，heapify函数实现如下:
var heapify = function(array, heapSize, i){
var left = i * 2 + 1,
right = i * 2 + 2,
largest = i;
if (left < heapSize && array[left] > array[largest]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest !== i) {
swap(array, i, largest);
heapify(array, heapSize, largest);
}
};
堆构造好之后，就可以应用堆排序的算法了，也就是行{2}和行{3}。
