堆

堆（Heap）是一种特殊的完全二叉树，它满足两个主要特性：结构性和堆序性。根据堆序性的不同，堆可以分为最大堆和最小堆：

1. 最大堆：任何一个父节点的值都大于或等于它的子节点的值。
2. 最小堆：任何一个父节点的值都小于或等于它的子节点的值。

结构性

堆作为一种完全二叉树，其所有的层都有节点填满，除了最下层。最下层的节点从左到右填充，这保证了树的平衡，从而使得堆能在对数时间内完成插入和删除的操作。

堆序性

堆序性质确保了树的根节点（对于最大堆来说）总是整个树中的最大元素，这使得堆非常适合实现优先队列，因为可以快速访问到优先级最高的元素。

基本操作

• 插入（Heapify-Up）：新元素被添加到树的末尾，然后向上移动（如果必要的话），以保持堆的性质。这个过程又称为上浮（Heapify-Up）。
• 删除最大元素/最小元素（Heapify-Down）：对于最大堆来说，最大元素总是位于根节点。删除根节点后，通常将最后一个元素移动到根节点的位置，然后向下移动（如果必要的话），以保持堆的性质。这个过程又称为下沉（Heapify-Down）。

存储

堆通常通过数组来实现。对于数组中的任意元素arr[i]：

• 其左子节点在位置2*i + 1；
• 其右子节点在位置2*i + 2；
• 其父节点在位置(i - 1) / 2。

应用

• 优先队列：堆是实现优先队列的理想数据结构，支持快速访问和删除最大元素（最大堆）或最小元素（最小堆）的操作。
• 堆排序：利用堆可以高效地进行排序，称为堆排序（Heapsort），这是一种时间复杂度为O(n log n)的排序算法。
• 图算法：在Dijkstra和Prim算法中用于找到未访问节点中的最小距离/最小边。

堆结合了数组的高效空间利用和树的高效操作性能，是实现多种算法和数据结构的基础。