heap

堆（通常指数据结构中的堆，如二叉堆）是一种特殊的树形数据结构，具有以下关键属性：

1. 结构属性

• 完全二叉树：
  堆必须是一棵完全二叉树。即除了最后一层外，其他层的节点都是满的，且最后一层的节点尽可能向左对齐。
  • 这一特性使得堆可以用数组高效实现，无需指针。
  • 数组索引规则（假设根节点索引为 0）：
    • 父节点 i 的左子节点索引：2i + 1
    • 父节点 i 的右子节点索引：2i + 2
    • 子节点 i 的父节点索引：⌊(i-1)/2⌋

2. 堆序属性

堆分为最大堆和最小堆，满足以下顺序关系：

• 最大堆：每个父节点的值 ≥ 其子节点的值（根节点为最大值）。
• 最小堆：每个父节点的值 ≤ 其子节点的值（根节点为最小值）。

注意：堆序属性仅约束父子节点，不要求兄弟节点之间有序。

3. 核心操作与时间复杂度

• 插入元素：
  1. 将新元素添加到末尾。
  2. 上浮（Percolate Up）：逐层与父节点比较并交换，直到满足堆序。
     时间复杂度：O(log n)。
• 提取根节点（删除最大值或最小值）：
  1. 移除根节点，将最后一个元素移到根位置。
  2. 下沉（Percolate Down）：逐层与较大（或较小）的子节点交换，直到满足堆序。
     时间复杂度：O(log n)。
• 构建堆：
  从最后一个非叶子节点开始，自底向上执行下沉操作。
  时间复杂度：O(n)（优于逐个插入的 O(n log n)）。

4. 应用场景

• 优先队列：快速获取和删除最高/低优先级元素。
• 堆排序：时间复杂度 O(n log n) 的原地排序算法。
• 图算法：如 Dijkstra 最短路径算法、Prim 最小生成树算法。

5. 与其他结构的对比

• 二叉搜索树（BST）：
  BST 要求左子树 < 父节点 < 右子树，支持高效查找任意元素（O(log n)），但堆仅维护父子关系，牺牲查找效率以优化插入/删除最值的速度。
• 优先队列：
  堆是优先队列的标准实现，因其在动态数据中高效维护最值。

6. 局限性

• 不支持快速查找：查找任意元素需 O(n) 时间。
• 仅维护最值：除根节点外，其他节点无全局有序性。

总结：堆通过完全二叉树结构、堆序属性和高效的上浮/下沉操作，实现了快速插入、删除最值的功能，是优先队列和堆排序等算法的核心数据结构。