二叉堆详解：插入删除操作全解析

## 二叉堆详解：插入与删除操作全解析 想深入了解二叉堆？本文将带你全面认识这种高效的数据结构。二叉堆本质上是一种用数组实现的完全二叉树，巧妙地通过“上浮”和“下沉”操作，实现了O(log N)时间复杂度的插入和删除操作，在最小堆和最大堆之间灵活切换，满足不同的最值需求。文章将详细解析二叉堆的插入与删除机制，并通过实例讲解如何维护堆的特性，确保其在优先队列、堆排序、Dijkstra算法、Prim算法以及Top K问题等常见应用场景中发挥出色性能。掌握二叉堆，提升你的算法效率！

二叉堆是一种用数组实现的完全二叉树，满足堆属性，分为最小堆和最大堆，能高效插入、删除并获取最值，时间复杂度为O(log N)；其核心操作为插入时的“上浮”和删除堆顶时的“下沉”；常见应用包括优先队列、堆排序、Dijkstra与Prim算法及Top K问题。

二叉堆本质上是一种特殊的完全二叉树，它满足堆属性：要么每个父节点的值都小于或等于其子节点（最小堆），要么每个父节点的值都大于或等于其子节点（最大堆）。在我看来，它就是一种巧妙的数据结构，能让我们高效地找到集合中的最大或最小元素，并且在添加或移除元素时也能保持这种特性。

解决方案

说起二叉堆，它其实就是用数组实现的完全二叉树。这种实现方式非常精妙，因为它省去了显式的指针，通过简单的数学计算就能找到父节点和子节点。比如，对于一个索引为 i 的节点（从0开始计数），它的左子节点在 2*i + 1，右子节点在 2*i + 2，而它的父节点则在 (i - 1) / 2（向下取整）。这种结构保证了树的紧凑性，也为堆操作的高效性打下了基础。

我们通常说的二叉堆，其实有两种：最小堆（Min-Heap）和最大堆（Max-Heap）。最小堆的根节点是所有元素中最小的，且每个父节点都比它的子节点小；最大堆则相反，根节点最大，且每个父节点都比它的子节点大。这种特性让它在需要频繁获取最值，同时又不断有元素进出的场景下显得格外有用。

二叉堆的插入操作是怎样实现的？

二叉堆的插入操作，在我看来，核心思想就是“先安家，再找位”。具体来说，当你有一个新元素要加入堆时，我们第一步是把它放到堆的“最后”一个位置，也就是数组的末尾。这保证了堆的“完全二叉树”结构不会被破坏。

接着，才是真正有趣的部分：这个新来的元素可能不符合堆的属性（比如在最小堆里，它可能比它的父节点还小）。这时候，我们就需要让它“上浮”（或者叫“上滤”、“冒泡”）。这个过程就是不断地将新元素与其父节点进行比较：如果新元素比父节点更符合堆的属性（例如，在最小堆中，新元素比父节点小），就交换它们的位置。这个过程会一直重复，直到新元素到达根节点，或者它不再比父节点更符合堆的属性为止。

举个例子，假设我们有一个最小堆，要插入一个值。我们把它加到数组末尾，然后从这个位置开始，向上检查。如果新元素比父节点小，就交换；然后继续向上，直到它不再小于父节点，或者到达了堆顶。这个“上浮”操作的时间复杂度是 O(log N)，因为我们每次都沿着树的高度向上移动。

二叉堆的删除操作（以删除堆顶元素为例）如何进行？

二叉堆的删除操作，尤其是删除堆顶元素（这通常是最常见的删除场景，因为堆就是为了快速获取最值），逻辑上稍微复杂一点，但同样巧妙。它的基本思路是“移花接木，再重排”。

删除堆顶元素，我们不能直接把根节点挖掉，因为那样会留下一个空缺，而且还可能破坏完全二叉树的结构。所以，我们的做法是：把堆的最后一个元素（也就是数组的最后一个元素）挪到根节点的位置，然后把原来的根节点（现在是最后一个元素）从数组中移除。这样，我们既移除了目标元素，又保持了完全二叉树的结构。

然而，新的根节点可能不符合堆的属性（比如在最小堆里，它可能比它的子节点大）。这时候，我们就需要让它“下沉”（或者叫“下滤”、“堆化”）。这个过程是：将当前节点与其子节点进行比较，找出其中最符合堆属性的子节点（例如，在最小堆中，找出最小的子节点）。如果当前节点比这个子节点更不符合堆属性（例如，在最小堆中，当前节点比最小的子节点还大），就交换它们的位置。然后，继续对交换后的新位置重复这个过程，直到当前节点不再比其子节点更不符合堆属性，或者它已经到达了叶子节点。

这个“下沉”操作同样是 O(log N) 的时间复杂度，因为它沿着树的高度向下移动。通过这种方式，二叉堆在删除堆顶元素后，依然能高效地恢复其堆特性。

二叉堆在实际应用中有哪些常见场景？

二叉堆的应用场景非常广泛，它不仅仅是一种理论上的数据结构，在很多实际问题中都扮演着核心角色。

首先，最典型的应用就是实现优先队列。优先队列是一种抽象数据类型，它允许我们以优先级的方式访问元素，而二叉堆恰好能高效地支持这种操作：插入元素（O(log N)）和取出最高优先级元素（O(1) 获取，O(log N) 删除）。在操作系统中，任务调度器常常用优先队列来决定哪个任务应该先执行；在模拟系统中，事件队列也常用它来管理事件的发生顺序。

其次，堆排序（Heap Sort）是另一种基于二叉堆的经典排序算法。它利用堆的特性，先将所有元素构建成一个堆，然后重复地取出堆顶元素（最大或最小），并将其放到数组的末尾，最终实现排序。堆排序是一种原地排序算法，时间复杂度稳定在 O(N log N)，在一些对内存要求严格的场景下很有优势。

再者，在图算法中，二叉堆也大放异彩。比如著名的迪杰斯特拉（Dijkstra）算法用于寻找最短路径，以及普利姆（Prim）算法用于寻找最小生成树，它们都可以利用优先队列（底层用二叉堆实现）来高效地选择下一个要处理的顶点或边，从而显著优化算法的性能。

最后，在一些数据流或大数据场景下，二叉堆也常用于解决“Top K”问题，也就是从海量数据中找出最大或最小的 K 个元素。我们可以维护一个大小为 K 的最小堆（如果找最大的 K 个），遍历数据流，如果当前元素比堆顶元素大，就替换堆顶并重新堆化。这样，堆中始终维护着当前最大的 K 个元素，而空间复杂度仅为 O(K)。这比把所有数据都加载到内存中再排序要高效得多。

总的来说，二叉堆的这些特性让它成为计算机科学中一个非常实用且高效的工具。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《二叉堆详解：插入删除操作全解析》文章吧，也可关注golang学习网公众号了解相关技术文章。