成都网站建设重庆最加科技中建八局第一建设有限公司青岛分公司

7.1 相关概念

        堆（Heap）在计算机科学中是一种特殊的数据结构，它通常被实现为一个可以看作完全二叉树的数组对象。以下是一些关于堆的基本概念：

数据结构：

        堆是一个优先队列的抽象数据类型实现，通过完全二叉树的逻辑结构来组织元素。
完全二叉树意味着除了最后一层外，每一层都被完全填满，并且最后一层的所有节点都尽可能地集中在左边。
物理存储：

        堆用一维数组顺序存储，从索引0开始，每个节点的父节点和子节点之间的关系可以通过简单的算术运算确定。
堆的特性：

        堆序性质：对于任意节点i，其值（或关键字）满足与它的子节点的关系——在最大堆（大根堆）中，节点i的值大于或等于其两个子节点的值；在最小堆（小根堆）中，节点i的值小于或等于其两个子节点的值。
结构性：堆始终保持完全二叉树的状态，这意味着即使有节点删除或插入，堆也要经过调整以保持堆序性质。
操作：

        插入：新元素添加到堆中时，需要自下而上调整堆，以确保新的元素不会破坏堆的性质。
        删除：通常从堆顶（根节点）删除元素（即最大堆中的最大元素或最小堆中的最小元素），然后将堆尾元素移动到堆顶，再自上而下调整堆。
        查找：堆常用于快速找到最大或最小元素，但查找特定值的时间复杂度通常不优于线性时间，因为堆本身不具备随机访问的能力。
应用：

        堆常用于解决各种问题，如优先级队列、事件调度、图算法中的最短路径计算（Dijkstra算法）、求解Top K问题等。
分类：

        最常见的堆是二叉堆，包括大根堆和小根堆。
        还有其他类型的堆，比如斐波那契堆，提供更高效的合并操作以及其他优化特性。

建堆算法：

       1. Dijkstra算法：是一个使用优先队列（可以基于堆实现）的经典例子。在Dijkstra算法中，每次都会从未确定最短路径且当前距离已知最小的顶点开始，更新与其相邻顶点的距离。为了高效地找到下一个待处理的顶点（即当前已知最短路径的顶点），会用到一个能够根据顶点距离值进行快速插入和删除的优先队列，堆就是实现这种功能的理想数据结构之一。

       2. 堆下沉”（Heap Sink），“堆下滤”（Heap Percolate Down）：从根节点（非叶子节点中最高层的一个）开始。 检查该节点与其两个子节点的关系：在最大堆中，如果当前节点的值小于其任意一个子节点的值；在最小堆中，如果当前节点的值大于其任意一个子节点的值。 如果违反了堆的性质，则交换当前节点与其较大（对于最大堆）或较小（对于最小堆）子节点的值，并将当前节点移动到新位置（即原来子节点的位置）。 重复上述步骤，但这次以交换后的子节点作为新的当前节点，继续下潜至当前节点没有子节点（即成为叶子节点），或者当前节点及其子节点均满足堆的性质为止。

时间复杂度：