完成了 JavaScript 数据结构课程，以下是我学到的关于二叉堆的知识。什么是二叉堆？基本实现 结论 参考

2025-06-07

完成了 JavaScript 数据结构课程，以下是我学到的关于二叉堆的知识。

什么是二叉堆？

基本实现

结论

参考

在上一篇文章中，我写了关于二叉搜索树的文章，并尝试将其实现到我的 Chrome 扩展程序中。简单的二叉搜索树对于我的项目来说并不完美，但是我发现树结构中的一些特性对项目很有用。

目前，我将主要数据作为对象存储在数组中，如下所示：


// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "cat1", id: "4", meaning: "information of the vocabulary.", tag: ["tag1", "tag2"], word: "Example Vocab 1"}
1: {category: "cat3", id: "3", meaning: "Hello World", tag: ["tag1", "tag4"], word: "Example Vocab 2"}
2: {category: "cat2", id: "2", meaning: "This is new vocabulary.", tag: ["tag4"], word: "Example"}
3: {category: "cat4", id: "1", meaning: "You can write anything.", tag: ["tag2", "tag4", "tag5"], word: "Sample"}
Enter fullscreen mode Exit fullscreen mode

在这种情况下，插入和删除操作的时间复杂度为 O(n)。因此，我仍然在寻找一个希望时间复杂度为 O(1) 的数据结构。

我在二叉搜索树之后学习了二叉堆。在本文中，我将思考它是否适合我。

什么是二叉堆？

堆是树数据类型中的一种，二叉堆又属于堆的一种。二叉堆的形式类似于二叉树。

树种

我们可以用数组来实现它，这样每个值都有一个索引。
与二叉搜索树相同，每个值有 0 到 2 个子节点，但不超过 2 个。

当二叉堆为最大二叉堆时，父节点总是大于子节点。当二叉堆为最小二叉堆时，父节点总是小于子节点。

最大二叉堆

这些特性使得二叉堆擅长寻找最大数，并且在移除最大数或插入新数时不断更新列表。

删除最大数量

当我们移除数组中最大的数字时，我们想知道下一个最大的数字是哪一个。我们或许可以直接看到其中一个子节点，并将其作为最大的数字，但这会打乱数组其余部分的顺序。

为了将下一个最大的数字放在列表的开头，同时又不弄乱列表，我们可以实现向下冒泡的方法。首先将数组中的最后一个数字放在列表的开头，然后我们可以将这个数字向下下沉，直到找到正确的位置。

最大二叉堆排序

泡泡下台阶

我们只需要几个步骤就可以对数组进行排序。

（1）取出数组中的最后一个数字（我们在这里称之为目标），并将其放在根节点。
（2）比较目标及其子节点。-
如果其中一个大于目标，则交换目标和较大的子节点。-
如果两个子节点都大于目标，则交换目标和最大的子节点。-
如果两个子节点都小于目标，那就是正确的位置。

插入数字

当我们向数组中添加一个新的随机数时，我们可以实现冒泡法来找出它的正确位置，并保持整个数组按应有的顺序排序。

泡泡舞步骤

它与泡腾法正好相反。

（1）首先，将新数字插入数组的末尾。
（2）比较目标数字和它的父数字。
- 如果父数字小于目标数字，则相互交换。
- 如果父数字大于目标数字，那么它就在正确的位置。

基本实现

我们将把它实现为一个数组，因此我们只需要初始化 MaxBinaryHeap 类。


class MaxBinaryHeap {
    constructor() {
        this.heap = [];
    }
}
Enter fullscreen mode Exit fullscreen mode

删除最大实施

当我们使用冒泡方法时，时间复杂度为 O(log n)。

removeMax() {
    let removed = this.heap[0];
    let end = this.heap.pop();
    if (this.heap.length > 0) {
        this.heap[0] = end;
        this.bubbleDown();
    }
    return removed;
}
Enter fullscreen mode Exit fullscreen mode

气泡向下实施

bubbleDown() {
    let targetIdx = 0;
    while (true) {
        let target = this.heap[targetIdx];
        let leftChildIdx = targetIdx * 2 + 1;
        let rightChildIdx = targetIdx * 2 + 2;
        let left = this.heap[leftChildIdx];
        let right = this.heap[rightChildIdx];
        let swap = null;
        if (leftChildIdx < this.heap.length && target < left){
            swap = leftChildIdx;
        }
        if (rightChildIdx < this.heap.length && target < right && left < right){
            swap = rightChildIdx;
        }
        if (swap === null) break;
        this.heap[targetIdx] = this.heap[swap];
        this.heap[swap] = target;
        targetIdx = swap;
    }
}
Enter fullscreen mode Exit fullscreen mode

插入实现

采用冒泡法插入也是 O(log n)。

insert(val) {
    this.heap.push(val);
    this.bubbleUp();
}
Enter fullscreen mode Exit fullscreen mode

气泡式实施

bubbleUp() {
    let targetIdx = this.heap.length - 1;
    let target = this.heap[targetIdx]
    while(targetIdx > 0){
        let parentIdx = Math.floor((targetIdx - 1) / 2);
        let parent = this.heap[parentIdx]
        if (target > parent) {
            this.heap[parentIdx] = target;
            this.heap[targetIdx] = parent;
            targetIdx = parentIdx;
        }
        if (target <= parent) break;
    }
}
Enter fullscreen mode Exit fullscreen mode

结论

优先级队列可以用二叉堆高效地实现，但在我的 Chrome 扩展程序中，它没有优先级，而且在移除列表中间元素时也需要高效。
这次我们不打算实现二叉堆，但堆这种数据结构本身的使用非常广泛，因此绝对值得实践一下。

参考

JavaScript 算法和数据结构大师班 (Udemy)
数据结构列表 (维基百科)

文章来源：https://dev.to/maikomiyazaki/completed-javascript-data-struct-course-and-here-is-what-i-learned-about-binary-heap-5a0i
Devto 翻译
PREV
完成了 JavaScript 数据结构课程，以下是我学到的关于图（+ Dijkstra 算法）的知识。首先，什么是图？如何用 JavaScript 实现图？基本实现：查找最短路径（Dijkstra 算法） 结论：资源
NEXT
别再在 GitHub 上推送你的 React API Key 了😪