基本概念
二叉堆（Binary Heap）实际上是一个完全二叉树或是近似完全二叉树，也就是每一个节点下面最多只会有两个字节点，也有可能是一个或没有。它长成下图这样：
在上图中，10 下方有 7 和 9，而 7 下方又有 2 和 1 两个数字，虽然 9 下方只有一个 6，但仍然符合二叉树的每个节点只有两个以下的子节点的规则，也就是说如果 9 以下连 6 都没有，也还是个二叉树，只要不超过三个就没问题。
二叉堆分成两种，分别是最大堆（max-heap）和最小堆（min-heap），最大堆就是所有节点的数字都大于它之下的数字。例如上图中，不论是 10 之下的 7 和 9、7 之下的 2 和 1 或者是 9 之下的 6，都不存在下方的数字比上方大的情况，所以就可以把图中的二叉堆称作最大堆。当所有的数字都比下方的数字要小时，则是最小堆。
二叉堆并不是什么新的数据结构，它只是个普通的数组而已，只是用了二叉堆的思维来处理排序。那么二叉堆中的每个数字是怎么对应到 Array 里的呢？先看看一张图：
上图中的橘色字代表的是 index，虽然二叉堆是个二叉树，但是它在 Array 里的位置会按照二叉堆中由上到下、从左到右做 index 的对应，而且还可以发现，在每一个最大堆的第一个节点（index 为 0 的数字） 都会是所有数字中最大的那个，所以只需要不停的重复“用剩下的数字生成最大堆”即可，那当比较完所有数字时，一个排序后的 Array 也就出现了。
排序过程
二叉堆排序的重点和精华是怎样使一个二叉树变成最大堆或最小堆。假设有一个二叉树：
首先从最后一个存在子节点的地方开始比较，在上图中就从是 index 为 2 的数字 9 开始，毕竟如果从 index 为 5 的 6 开始一点意义都没有，因为底下没有任何数字可以比较。所以比较的顺序是从 index 2 到 0。
一开始取出 index 为 2 的 9，让它与下方的数字比较，如果想要成为最大堆，那么下方如果有比 9 大的数字那就要交换位置，而 9 下方只有一个较小的 6，因此不需要做任何处理。
接下来取出 index 为 1 的 7，可以发现 7 右下方的数字 10 比 7 还要大，而左下方的 2 比 10 小，所以 10 与 7 必须要交换位置：
再继续比较之前，先来观察一下当前的二叉树中已经比较过的部分，不论是 9 与底下的数字或是 10 与底下的数字，它们都各自成为了一个独立的最大堆：
这表示我们每次比较的过程，都会让该 index 以下的的数字变成最大堆，也就是说，让一堆数字变成最大堆的过程，实际上是在寻找该其中的最大值。
当倒数第二层的数字都处理完成之后，就要把层数向上移，刚刚倒数第二层比较的 index 是 2 和 1，而再往上那层就只剩下 index 为 0 的 1 了，处理步骤和之前一样，先把 1 和底下右边的 9 进行比较，发现 9 会比 1 还要大，但是 1 底下还有左边的数字 10，而 10 又比 9 更大，所以要与 1 换位置的并不是 9，而是 10：
在这里需要注意，因为交换了 10 和 1 的位置，所以有可能会导致左下方的最大堆被破坏，随意必须要以原来 10 的那个位置（现在是数字 1）再去与下方做比较。1 先与右边 7 做比较，再与左边的 2 做比较，这其中的 7 会是最大的，因此 7 要与 1 换位置：
交换完成后 1 下面也没有其他数字了，所以也就不用交换了。
当完成最大堆/最小堆之后
从倒数第二层开始，经过不断的比较和交换位置一直到第一层，就可以得到一个最大堆，也就是 index 为 0 的数字是这堆数字中最大的一个，接下来就要排序出第二大的数字了。
首先要把当前最大的数字和最右下的数字交换位置，按照 index 的话就是把第一个数字移动到最后一个：
交换之后就要忽略已经排序过的 10，并用剩下的数字再生成一次最大堆：
即使少了 10，但经过比较后仍然会得到一个新的最大堆，这时在第一个位置上最大的数字是 9，因此 9 再与二叉堆中的最后一个数字 1 做交换：
接下来的步骤都是一样的，忽略 9 和 10 用剩下的数字生成最大堆：
接着会得到剩下数字中最大的 7，然后把 7 和最后一个 1 做交换，再忽略 7、9 和 10，用剩下的数字形成最大堆，一直到二叉堆中没有任何东西时就代表排序完成了（如果是最大堆最后会排序出由小到大的数字，最小堆则相反）：
所以用二叉堆进行排序的过程就是一直找出最大或最小数，然后移动到当前这堆数字的最后一个，之后将它忽略再继续寻找的过程。
除此之外还可以发现，因为每次都把最大的数字与最后一个数字交换，这会形成一个结果，那就是除了 index 为 0 的那个值之外，其他 index 与底下的数字一定还是维持着最大堆的二叉堆，两次把最大值换到二叉堆中最后一个数字后都是这样子。
所以如果完成了一次最大堆，那么接下来的每一次就不再需要从最后一个底下有数字的 index 开始生成最大堆，只要从 index 0 开始执行就行了。
代码实现
以下的代码以最大堆为例。
首先因为每个数字都要和底下的数字做比较，以形成一个个 max-heap，那既然 Binary Heap 的本体只是个 Array，那怎样才能知道每个 index 之下的 index 是多少呢？先回顾一下前面的对照图：
可以观察到，如果把每个数字所在的 index，分别做 index * 2 + 1 和 index * 2 + 2 的运算，就会得到左下或右下数字的 index，所以稍后就要把需要比较的 index 与 index * 2 + 1 和 index * 2 + 2 三个数字去比大小，把最大的数字和 index 交换位置就行了，在交换之后还要再接着检查下方被交换的 index 的最大堆是否被破坏掉。
接着是怎么找到最后一个底下有数字的 index。因为我们已经知道底下的数字分别为 index * 2 + 1 和 index * 2 + 2，那么反过来说，最后一个数字的 index 一定是某个数字的 index * 2 + 1 或 index * 2 + 2。
例如上图中 Array 有 6 个数字，所以最后一个数字的 index 是 5，我们可以用 5 减去掉 2 或 1 再除上 2 得到它上方数字的 index，那到底是要减去 1 还是减去 2 呢？
我们可以试着想一下，如果减 1 的话就是假设它是左下方的数字，所以如果是右边数字被减 1 就会多 0.5，因此要减 1 后除以 2 再向下取整。另一方面如果减 2 的话就是右下方的数字，在这情况下如果是左边的数字就会少 0.5，所以要向上取整。
代码如下：
const maxHeapify = (arr, i, size) => {
const leftIndex = i * 2 + 1;
const rightIndex = i * 2 + 2;
let largest = i;
console.log('current num', arr[largest], 'left', arr[leftIndex], 'right', arr[rightIndex]);
if (leftIndex <= size && arr[largest] < arr[leftIndex]) {
largest = leftIndex;
}
if (rightIndex <= size && arr[largest] < arr[rightIndex]) {
largest = rightIndex;
}
console.log('largest', arr[largest]);
if (i !== largest) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
console.log(`change ${arr[i]} and ${arr[largest]}`, nums);
maxHeapify(arr, largest, size);
}
};
const nums = [1, 7, 9, 2, 10, 6];
const lastParentNumIndex = Math.floor((nums.length - 2) / 2);
for (let i = lastParentNumIndex; i >= 0; i -= 1) {
maxHeapify(nums, i, nums.length - 1);
};
maxHeapify 负责比较当前和底下的左右数字，如果有比较大的话，那就要取出较大的那个换位置，然后换位置后又要确认在它之下的最大堆是否被破坏，所以要用被替换的位置再执行一次 maxHeapify。至于第三个参数 size 是为了控制已排序过的数字，当第二次开始需要忽略它们时会用到。
后面的循环就是从最后一个底下有数字的 index 开始跑循环执行 maxHeapify，一直到 index 变成 0 为止。在几个关键步骤输入了日志，可以查看比较和交换的过程：
在最后一次生成最大堆之后，需要把当前的最大值（index 为 0 的数字）与二叉堆中最后的数字交换，并要忽略该数字，以 index 0 形成新的最大堆，再交换、忽略并以 index 0 形成新的最大堆，一直到所有的数字都遍历完成为止，代码如下：
for (let i = 0; i < nums.length; i += 1) {
[nums[0], nums[nums.length - 1 - i]] = [nums[nums.length - 1 - i], nums[0]];
maxHeapify(nums, 0, nums.length - 2 - i);
}
console.log(nums); // [1, 2, 6, 7, 9, 10]
首先是用循环遍历 Array 内的所有数字，然后第一个数字和当前剩下的最后一个数字交换位置。例如在第一次，最大值要与 Array 的最后一个交换，第二次最大值要与 Array 的倒数第二个交换…依此类推，最后重复这个操作。
第 3 行代码就是从 index 0 的位置开始形成最大堆，并且二叉堆中的数字会越来越少，由 nums.length - 2 - i 控制，第一次只需要忽略最后一个已交换到最后的最大值，所以忽略一个，第二次就是忽略两个…传入 maxHeapify 的 size，这样超过 size 的数字就不会进行比较，直接被忽略。
等到所有的数字都比较完成后，Array 也就排序完成了。