# 前置知识：完全二叉树

完全二叉树是指同时满足下面两个条件的二叉树：

• 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
• 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。

完全二叉树可以是这样的：

也可以是这样的：

但不能是这样的：

更不能是这样的：

注意，完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从0开始进行编码：

那么对于索引为 n 的结点来说：

• 索引为 (n-1)/2 的结点是它的父结点
• 索引 2*n+1 的结点是它的左孩子结点
• 索为引 2*n+2 的结点是它的右孩子结点

# 什么是堆

堆是完全二叉树的一种特例。根据约束规则的不同，堆又分为两种：

• 大顶堆
• 小顶堆

如果对一棵完全二叉树来说，它每个结点的结点值都不小于其左右孩子的结点值，这样的完全二叉树就叫做“大顶堆”：

若树中每个结点值都不大于其左右孩子的结点值，这样的完全二叉树就叫做“小顶堆”

# 堆的基本操作：以大顶堆为例

大顶堆和小顶堆除了约束条件中的大小关系规则完全相反以外，其它方面都保持高度一致。现在我们以大顶堆为例，一起来看看堆结构有哪些玩法。

这里我给出一个现成的大顶堆：

很多时候，为了考察你对完全二叉树索引规律的掌握情况，题目中与堆结构同时出现的，还有它的层序遍历序列：

[9, 8, 6, 3, 1]

我们需要关注的动作有两个：

• 如何取出堆顶元素（删除操作）
• 往堆里追加一个元素（插入操作）

至于堆的初始化，也只不过是从空堆开始，重复执行动作2而已。因此，上面这两个动作就是堆操作的核心。

# 取出堆顶元素

取出元素本身并不难，难的是如何在删除元素的同时，保持住队的“大顶”结构特性。为了做到这点，我们需要执行以下操作：

• 用堆里的最后一个元素（对应图中的数字1）替换掉堆顶元素。
• 对比新的堆顶元素（1）与其左右孩子的值，如果其中一个孩子大于堆顶元素，则交换两者的位置：

交换后，继续向下对比1与当前左右孩子的值，如果其中一个大于1，则交换两者的位置：

重复这个向下对比+交换的过程，直到无法继续交换为止，我们就得到了一个符合“大顶”原则的新的堆结构：

上述这个反复向下对比+交换的过程，用编码实现如下（仔细看注释）：

// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function downHeap(low, high) {
    // 初始化 i 为当前结点，j 为当前结点的左孩子
    let i=low,j=i*2+1 
    // 当 j 不超过上界时，重复向下对比+交换的操作
    while(j <= high) {
        // 如果右孩子比左孩子更大，则用右孩子和根结点比较
        if(j+1 <= high && heap[j+1] > heap[j]) {
            j = j+1
        }
        
        // 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”
        if(heap[i] < heap[j]) {
            // 交换位置
            const temp = heap[j]  
            heap[j] = heap[i]  
            heap[i] = temp
            
            // i 更新为被交换的孩子结点的索引
            i=j  
            // j 更新为孩子结点的左孩子的索引
            j=j*2+1
        } else {
  

Preview