C++ 二叉堆

引言

二叉堆是计算机科学中常用的基本数据结构，用于高效实现优先级队列。它是一个完全二叉树，如果它是最小堆，则每个节点的值小于或等于其子节点；如果它是最大堆，则每个节点的值大于其子节点。

二叉堆

二叉堆通常表示为数组，其中父子关系基于数组元素的索引定义。在二叉堆中，对于索引 i 处的任何节点

• 其左子节点位于索引 2*i + 1 处。
• 其右子节点位于索引 2*i + 2 处。
• 其父节点位于索引 (i - 1) / 2 处。

二叉堆有两种类型：最小堆和最大堆。

• 在最小堆中，每个节点的值小于或等于其子节点的值。
• 在最大堆中，每个节点的值大于或等于其子节点的值。

二叉堆的关键属性是堆顺序属性，它确保根节点（索引 0 处）包含最小（或最大）元素（分别是最小堆或最大堆）。

构建

二叉堆通常表示为数组，其中索引 i 处的节点的子节点位于索引 2i+1 和 2i+2 处。这种表示允许高效存储和操作堆结构。考虑以下示例：

以数组形式，相同的堆将表示为：[5, 9, 11, 14, 18, 19, 21]。

二叉堆上的操作

• 插入： 当新元素添加到堆中时，它被放置在底部，保持完全二叉树属性。然后，通过将其与父节点进行比较并在必要时交换，将其“冒泡”或“上浮”到正确位置。
• 删除： 从堆中删除根元素。删除后，数组中的最后一个元素取代根的位置。然后，通过将其与子节点进行比较并在必要时交换，将其“下沉”或“下滤”到正确位置。
• 堆化： 此操作从给定数组构建堆。它从最后一个非叶节点开始，并执行“下沉”操作，直到所有节点都满足堆属性。
• 提取最大/最小： 此操作从堆中删除并返回最大（对于最大堆）或最小（对于最小堆）元素。它涉及删除根元素并重新排列堆以保持其属性。

实施

说明

• 该程序定义了一个 MinHeap 类来封装堆操作。
• 在 MinHeap 类中，有一个私有成员 heap，它是一个存储堆元素的向量。
• heapify 函数是一个辅助函数，用于维护最小堆属性。它以索引 i 作为输入，并递归地调整以索引 i 为根的子树，以确保它满足最小堆属性。
• insert 函数将新元素插入堆中。它首先将元素添加到向量的末尾，然后执行“冒泡”操作，将元素向上移动树，直到其父节点小于或等于它，从而确保维护最小堆属性。
• extractMin 函数从堆中删除并返回最小元素。它首先检查堆是否为空，如果为空则返回 -1（也可以抛出异常）。
• 然后，它用向量中的最后一个元素替换根（最小元素），删除最后一个元素，并对根调用 heapify 以恢复最小堆属性。
• 在 main 函数中，创建了一个 MinHeap 实例，并使用 insert 函数向其中插入了几个元素。然后，使用 extractMin 从堆中提取最小元素并打印到控制台。

程序输出

时间复杂度分析

• 插入 (insert)： 将元素插入二叉堆涉及将其添加到堆数组的末尾，然后执行 heapifyUp 操作，其时间复杂度为 O(log n)，其中 n 是堆中的元素数量。因此，插入的总体时间复杂度为 O(log n)。
• 提取 (extractMin)： 从最小堆中提取最小元素需要删除根节点并用堆数组的最后一个元素替换它。这之后是 heapifyDown 操作，其时间复杂度为 O(log n)，其中 n 是堆中的元素数量。因此，提取的总体时间复杂度为 O(log n)。
• 访问最小元素： 访问最小堆中的最小元素是常数时间操作，因为最小元素总是存储在根节点处。因此，访问最小元素的时间复杂度为 O(1)。

二叉堆的应用

二叉堆因其高效性而在各种算法和数据结构中得到应用

• 优先级队列： 二叉堆通常用于实现优先级队列，其中元素以相关优先级插入并按优先级顺序检索。
• 堆排序： 堆排序是一种基于比较的排序算法，它使用二叉堆高效地按升序（或降序）排序元素。
• Dijkstra 算法： 这种用于查找图中节点之间最短路径的算法使用优先级队列（通常使用二叉堆实现）来高效选择要探索的下一个节点。

优点

• 简单表示： 二叉堆可以使用数组高效表示，与基于树的表示相比，开销更少。
• 高效操作： 插入、删除和检索最大或最小元素可以在对数时间复杂度内完成。

结论

总之，C++ 中的二叉堆数据结构为维护优先级队列提供了高效的解决方案，可以快速访问最高（或最低）优先级的元素。通过其平衡的树结构和堆属性，二叉堆为元素的插入和提取提供了对数时间复杂度，使其适用于需要快速访问优先级数据的广泛应用。

通过实现堆操作（如插入、删除和堆化函数），开发人员可以利用二叉堆的强大功能来优化算法并提高各种软件项目的整体性能。作为计算机科学和编程中的基本工具，掌握 C++ 中二叉堆的概念和实现为优雅高效地解决复杂问题打开了大门。