二叉堆

[S-T-D]

• 完全二叉树
  • 完全二叉树的数组表示
• 二叉堆的定义
  • 堆
  • 二叉堆
• 二叉堆的操作
  • 上浮（swim）
    • 代码实现
  • 下沉（sink）
    • 代码实现
  • 构建堆
    • 代码实现
• 复杂度
  • 时间复杂度
    • 添加、删除节点
    • 构建堆
  • 空间复杂度
• 参考资料
   

完全二叉树

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有 N 个节点的完全二叉树的深度为 logN + 1。深度为 k 的完全二叉树，至少有 2^(k - 1) 个节点，至多有 2^k - 1 个节点。—— 维基百科

简单来说，完全二叉树的每一层的节点都是满的，除了最后一层，最后一层缺少的节点只能出现在右边，不能出现在左边和中间。

举例：

        6
      /   \
     8     9
    / \   / \
   7   2 1   5
  / \
 3   4 

除了最后一层，其余层的节点都是满的，最后一层的节点从左往右排列，残缺的节点不能出现在中间和左边。
  
所以，下面这棵树就 不是 完全二叉树。

        6
      /   \
     8     9
    / \   / \
   6   2 1   5
  / \       /
 6   8     7

完全二叉树的数组表示

因为完全二叉树自身的特点（各个节点从上往下，从左往右依次排列），可以使用数组来表示一颗完全二叉树。

      6
    /   \
   8     9
  / \   / \
 7   2 1   5

这是一颗完全二叉树，按照从上到下、从左往右的顺序
可以将其转换为数组表现形式：[6, 8, 9, 7, 2, 1, 5]

通过数组来表示完全二叉树后，相应地，可以使用索引来表示各个节点的关系：

已知一个节点的索引是 i，那么
父节点的索引 = (i - 1) / 2
左子节点的索引 = 2 * i + 1
右子节点的索引 = 2 * i + 2

 

二叉堆的定义

堆

堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。—— 维基百科

二叉堆

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。—— 维基百科

当没有特殊说明时，都用二叉堆来指代堆。

二叉堆同样必须满足是一颗完全二叉树。

• 最大堆

  任意节点大于等于它的所有后裔，最大节点是树的根节点：

          8
        /   \
       7     6
      / \   / \
     5   4 3   1

• 最小堆

  任意节点小于等于它的所有后裔，最小节点是树的根节点：

          1
        /   \
       2     3
      / \   / \
     4   5 6   7

 

二叉堆的操作

下面介绍的所有操作，都基于最大堆进行。

上浮（swim）

理想情况下，一个二叉堆是有序的，任意父节点都大于等于其子节点以及子节点的子节点...。

上浮用于解决二叉堆在末尾添加节点的问题。

下面这是一颗有序的二叉堆：

       10
      /   \
     9     8
    / \   / \
   7   6 5   4
  / 
 3    

现在想要添加一个节点 12 到堆的末尾，也就是作为 7 的右子节点：

       10
      /   \
     9     8
    / \   / \
   7   6 5   4
  / \
 3  12 

添加以后，就破坏了二叉堆的有序状态，因为任意节点不再大于等于其后的子节点。

从肉眼可以判断，有序状态下 12 应该位于根节点的位置。

从代码操作来看，就需要将 12 上浮到根节点的位置，先和 7 交换位置，再和 9 交换位置，最后和 10 交换位置。

这个过程中节点 12 一步一步向上移动，所以形象地称为上浮。

上浮操作以后，二叉堆变为如下，又重新会到了有序状态：

       12
      /   \
     10    8
    / \   / \
   9   6 5   4
  / \
 3   7 

代码实现

/**
 * 上浮，对末尾节点进行上浮操作
 * @param {number[]} tree 二叉堆数组
 */
function swim(tree) {
    let posi = tree.length - 1;
    // 父节点索引
    let parentPosi;
    while (posi > 0) {
        parentPosi = Math.floor((posi - 1) / 2);
        // 如果父节点小于当前节点，就交换，并更新 posi
        if (tree[parentPosi] < tree[posi]) {
            swap(tree, parentPosi, posi);
            posi = parentPosi;
        } else {
            break;
        }
    }
}

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

下沉（sink）

下沉用于解决二叉堆删除节点的问题，删除过程和插入过程相反，指删除堆的头节点也就是最大元素，删除以后将末尾的节点移动到头节点的位置，移动以后打破了堆的有序状态，需要将新的头节点下沉到合适的位置

       12
      /   \
     10    8
    / \   / \
   9   6 5   4
  / \
 3   7 

删除头节点 12，将末尾节点 7 作为新的头节点：

        7
      /   \
     10    8
    / \   / \
   9   6 5   4
  / 
 3    

此时，堆不再有序，需要对新的头节点进行下沉操作，首先将 7 和它对子节点中较大的一个 10 交换，然后再和 9 交换，堆重新回到了有序状态：

       10
      /   \
     9     8
    / \   / \
   7   6 5   4
  / 
 3    

代码实现

/**
 * 下沉，对根节点执行下沉操作
 * @param {number[]} tree 二叉堆
 */
function sink(tree) {
    let posi = 0, index;
    // 末尾元素的索引
    const end = tree.length - 1;
    // 如果左子节点满足，进入循环
    while ((index = 2 * posi + 1) <= end) {
        // 选择左右子节点中较大的一个
        if (index + 1 <= end && tree[index] < tree[index + 1]) index++;
        // 如果父节点大于较大的子节点，结束循环
        if (tree[index] < tree[posi]) break;
        swap(tree, index, posi);
        posi = index;
    }
}

 

构建堆

上浮和下沉操作都是对二叉堆的修复操作，将局部无序的二叉堆修复成整体有序。

而构建是将一颗无序的完全二叉树变成整体有序的二叉堆。

比如，有如下一颗完全二叉树，现在想要将其有序化成二叉堆：

        5
      /   \
     2     7
    / \   / \
   10  6 1   4
  /  \
 8    3

想要让整体有序，可以先使其局部有序，每个局部都有序后，整体自然就有序了。

所以，可以将整棵树看作由 4 颗小树组成，分别是：

  5       2       7       10
 / \     / \     / \      / \
2   7   10  6   1   4    8   3

我们可以从后往前，分别对这 4 颗树的根节点进行下沉操作，后面两棵树进行下沉操作后没有变化。

接着对第二颗树 tree(2, 10, 6) 进行下沉操作之后，变为：

 10       
 / \   
2   6

注意，因为所有操作都是基于数组的索引，对第二颗树 tree(2, 10, 6) 的有序化操作，间接破坏了最后一棵树 tree(10, 8, 3) 的有序化，使其变为：

  2       
 / \   
8   3

所以，在对一颗树进行有序化后，如果后面的树的有序状态被破坏，需要接着对后面再次进行有序化操作，这样直到进行到第一颗树为止。

代码实现

sink 函数有小的变化，前面的 sink 默认从根节点开始执行，这里的 sink 从指定的节点开始。

/**
 * 将数组表示的完全二叉树构建成二叉堆
 * @param {number[]} tree 数组
 */
function buildBinaryHeap(tree) {
    const end = tree.length - 1;
    let posi = Math.floor((end - 1) / 2)
    // 从后往前计算出每一个有子节点的节点，对其进行下沉操作
    while (posi >= 0) {
        sink(tree, posi--);
    }
}

/**
 * 对指定节点进行下沉
 * @param {number[]} tree 二叉堆
 * @param {number} posi 需要进行下层操作的元素的索引
 */
function sink(tree, posi) {
    let index;
    // 末尾元素的索引
    const end = tree.length - 1;
    // 如果左子节点满足，进入循环
    while ((index = 2 * posi + 1) <= end) {
        // 选择左右子节点中较大的一个 
        if (index + 1 <= end && tree[index] < tree[index + 1]) index++;
        // 如果父节点大于较大的子节点，结束循环
        if (tree[index] < tree[posi]) break;
        swap(tree, index, posi);
        posi = index;
    }
}

 

复杂度

时间复杂度

添加、删除节点

还是以一个二叉堆为例：

       10
      /   \
     9     8
    / \   / \
   7   6 5   4
  / 
 3    

添加节点：

当在末尾添加节点的时候，最多需要多少次比较和多少次交换才能使堆有序呢？

比如添加的节点是 20，那么需要分别和 7、9、10 比较并且交换。

所以，求添加节点操作的时间复杂度相当求树的高度。

删除节点：

同样，删除根节点后，将末尾节点移动到根节点的位置。最坏情况下，需要将新的根节点下沉到树的底部。

所以，同样也是求树的高度。

 

那么，大小为 N 的完全二叉树的高度是多少呢？

已知高度为 n 的完全二叉树最多有 2^n - 1 个节点。

所以，N = 2^n - 1 => n = logN + 1。

大小为 N 的完全二叉树的高度为 logN + 1。

最后

• 添加节点：O(logN)，N 为节点数量。最多需要 logN 次比较和 logN 次交换操作。

• 删除节点：O(logN)。一个节点下沉一次，需要两次比较（两个子节点相互比较一次再和该节点比较一次）和一次交换。最多需要 2logN 次比较和 logN 次交换操作。

 

构建堆

还是以一个二叉堆为例：

这里令 n 为节点数量。

因为我们采用的是自底向上的使用 sink 来构建堆，所以：

对于最底层的 n/2 个节点来说，需要下沉 0 次

对于次底层的 n/4 个节点来说，需要下沉 1 次

对于第二层的 n/8 个节点来说，需要下沉 2 次

...

所以，总的的执行次数 S = 0 * n/2 + 1 * n/4 + 2 * n/8 + ...。

这是一个高中常见的、等差数列与等比数列逐项相乘后求和的问题。解法为两边同乘以公比（或其倒数）后与原式错位相减。

2S = 0 * n + 1 * n/2 + 2 * n/4 + ...

2S - S = 1 * n/2 + 1 * n/4 + 1 * n/8 + ...

最后用等比数列的求和公式可以得出：

S = n

所以，构建一个二叉堆的时间复杂度是 O(n)。

 

空间复杂度

O(1)，没有使用额外空间。

 

参考资料

• 《算法（第4版）》
• 维基百科
• 漫画：什么是二叉堆？（修正版）
• 为什么建立一个二叉堆的时间为O(N)而不是O(Nlog(N))? - 王赟 Maigo的回答 - 知乎