本篇分享的内容为堆排序，提到堆排序就不得不提一下堆这个数据结构。 堆实际上是一棵完全二叉树，因此其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
如果你不知道完全二叉树，那可以去搜索一下或者等我后续的文章，我会详细介绍树这种数据结构。言归正传，既然现在知道了堆，那如何使用js来描述呢。下面我用数组的结构来实现一个大顶堆：
function heapify(arr, i, len) {
let max = i,//双亲
left = 2 * i + 1, //左孩子
right = 2 * i + 2;// 右孩子
console.log('i: ', i);
console.log('left: ', left);
console.log('right: ', right);
if (len > left && arr[left] > arr[max]) {//左孩子存在，并且左孩子大于双亲，则最大值为左孩子
max = left;
}
if (len > right && arr[right] > arr[max]) {//右孩子存在，并且右孩子大于双亲，则最大值为右孩子
max = right;
}
if (max !== i) { //如果双亲不是最大值，则双亲和当前的最大值交换，并重新排序比较。
swap(arr, i, max);
heapify(arr, max, len);
}
//经过这样一轮之后，就构建了一个完整的双亲和孩子结构。
return arr;
}
// 建堆
let len = arr.length;
for (let i = parseInt(len / 2) - 1; i >= 0 ; i --) {
// 从最下面一层，一层一层往上建堆，这样就保证了上面一层一定比下面一层的左右孩子大
heapify(arr, i, len);
console.log(arr);
}
上面的代码我都有详尽的注释，有一点必须要注意，就是建大顶堆必须从下往上建，这样才能保证堆顶为最大值，也就是let i = parseInt(len / 2) - 1；为什么i要为parseInt(len / 2) - 1；这也是有道理的，因为完全二叉树的有这么两个性质：
性质1：在二叉树的第i层上至多有2^(i-1)个结点
性质2：深度为k的二叉树最多有2^k - 1个结点
也就是说最下层元素为总元素个数加一然后除二。具体为什么，可以从以2为指数的等比数列求和得知，这里就不一一展开。当然我这里讲的是满二叉树的情况，额，满二叉树就是完全二叉树的一种特殊情况。算了，具体概念这里就不深究了，以后再一一讲明。现在建好了大顶堆，那就开始关键性的步骤--堆排序。
堆排序的核心思想是：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码如下：
for (let j = len - 1; j >= 0; j --) {
swap(arr, 0, j);
heapify(arr, 0, j);
}
是不是很简单，是不是很清晰，好了，堆排序就是这样简单明了清晰，代码合在一起如下所示：
// var swap = require('./swap.js');
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
count = 0;
function heap(arr) {
// 建堆
let len = arr.length;
for (let i = parseInt(len / 2) - 1; i >= 0 ; i --) {
// 从最下面一层，一层一层往上建堆，这样就保证了上面一层一定比下面一层的左右孩子大
heapify(arr, i, len);
}
for (let j = len - 1; j >= 0; j --) {
swap(arr, 0, j);
heapify(arr, 0, j);
}
return arr;
}
function heapify(arr, i, len) {
let max = i,//双亲
left = 2 * i + 1, //左孩子
right = 2 * i + 2;// 右孩子
if (len > left && arr[left] > arr[max]) {//左孩子存在，并且左孩子大于双亲，则最大值为左孩子
max = left;
}
if (len > right && arr[right] > arr[max]) {//右孩子存在，并且右孩子大于双亲，则最大值为右孩子
max = right;
}
if (max !== i) { //如果双亲不是最大值，则双亲和当前的最大值交换，并重新排序比较。
swap(arr, i, max);
heapify(arr, max, len);
}
//经过这样一轮之后，就构建了一个完整的双亲和孩子结构。
return arr;
}
var arr=[91,60,96,13,35,63,324,223,23,44,22,90, 25,45];
console.log(heap(arr));
console.log(count);
堆排序就分享完了，堆排序的难点在创建堆，只要建好堆结构那剩下的排序就简单明了了。好了，今天就到这里了。预告一下下一篇内容为计数排序，唯一不需要比较的排序哦，thx~
