大小顶堆总结

大顶堆（Max Heap）和小顶堆（Min Heap）是两种基于完全二叉树的堆数据结构，它们用于实现高效的优先队列。

大顶堆（Max Heap）

大顶堆是一种堆数据结构，其中每个节点的值都不小于其子节点的值。换句话说，根节点的值是整个堆中的最大值。

特点：

1. 完全二叉树：大顶堆是一棵完全二叉树。
2. 节点关系：对于堆中的每个节点，父节点的值总是大于或等于其任何一个子节点的值。
3. 最大值在根节点：堆顶（根节点）是最大值，方便快速访问最大元素。

常见操作：

• 插入：在堆底添加一个新元素，然后向上调整以保持堆性质。
• 删除最大值：移除根节点，将最后一个节点放到根的位置，然后向下调整以保持堆性质。
• 堆排序：利用堆构建有序数据序列，通常通过构建大顶堆来实现升序排列。

小顶堆（Min Heap）

小顶堆是一种堆数据结构，其中每个节点的值都不大于其子节点的值。换句话说，根节点的值是整个堆中的最小值。

特点：

1. 完全二叉树：小顶堆也是一棵完全二叉树。
2. 节点关系：对于堆中的每个节点，父节点的值总是小于或等于其任何一个子节点的值。
3. 最小值在根节点：堆顶（根节点）是最小值，方便快速访问最小元素。

常见操作：

• 插入：在堆底添加一个新元素，然后向上调整以保持堆性质。
• 删除最小值：移除根节点，将最后一个节点放到根的位置，然后向下调整以保持堆性质。
• 优先队列：常用于实现优先队列，以快速访问和删除最小元素。

应用场景

• 优先队列：堆被广泛用于优先队列中，因为它能在 O(log n) 时间复杂度内插入元素和删除最大或最小元素。
• 堆排序：利用堆的特性实现排序算法。
• 图算法：如Dijkstra算法、Prim算法中用于高效获取当前最小（或最大）边。

这两种堆结构在具体实现中通常使用数组来实现，通过索引计算来找到父子节点的位置，从而节省内存和提高效率。