什么是堆（Heap）？

想象一下你有一群数字（或者其他可以比较大小的东西），你总是想快速地找到其中“最小”或“最大”的那个。

堆就是一种特殊的数据结构，它能非常高效地帮你做到这一点！它本质上是一个完全二叉树（Complete Binary Tree），并且满足一个特殊的性质：

核心性质：堆序性（Heap Property）

1. 小根堆（Min Heap）： 树中每个节点的值都小于或等于其子节点的值。这意味着，堆顶（根节点）总是最小的元素。
2. 大根堆（Max Heap）： 树中每个节点的值都大于或等于其子节点的值。这意味着，堆顶（根节点）总是最大的元素。

(图示：左为小根堆，右为大根堆。图片来源：维基百科，仅作示意)

---

堆的结构和存储

虽然堆看起来像一棵树，但在计算机中，我们通常用一个数组来存储它，这非常巧妙：

1. 根节点：通常存储在数组的第一个位置（如果数组从索引 1 开始）。
2. 父子关系：如果一个节点存储在数组的第 i 个位置（i > 1）：
   • 它的父节点在位置：$\lfloor \frac{i}{2} \rfloor$
   • 它的左子节点在位置：$2i$
   • 它的右子节点在位置：$2i + 1$

这种存储方式让我们可以不用指针就能快速地找到父子节点！

---

堆的主要操作

堆最核心的两个操作就是：插入元素和取出（删除）堆顶元素。

1. 插入元素（put 操作）

当你往堆里放入一个新的数字时，这个数字可能会“破坏”原来的堆序性。因此，我们需要进行调整，这个过程叫做**“上浮”（或“上滤”**）。

步骤（以小根堆为例）：

1. 把新元素放到数组的末尾，即作为堆的最后一个叶子节点。
2. 将这个新元素和它的父节点进行比较。
3. 如果新元素比父节点小（违反了小根堆性质），就和父节点交换位置。
4. 重复第 2、3 步，直到它到达根节点（now > 1）或者它不再比父节点小为止（堆序性恢复）。

💡 代码示例（自定义小根堆插入）

您提供的自定义插入函数 put(int d) 实现了这个“上浮”过程：

void put(int d) // heap[1]为堆顶
{
    int now, next;
    heap[++heap_size] = d; // 1. 放到末尾
    now = heap_size;
    while (now > 1)
    {
        next = now >> 1; // next 是 now 的父节点 (i/2)
        if (heap[now] >= heap[next]) break; // 3. 如果比父节点大或相等，停止
        swap(heap[now], heap[next]); // 4. 交换
        now = next; // 继续往上
    }
}

🛠️ C++ STL 标准库实现

C++ 标准库（需要 <algorithm> 和 <functional> 头文件）也提供了高效的堆操作。push_heap 函数就是用来执行插入后的“上浮”操作：

// 小根堆的 STL 插入
void put(int d)
{
    heap[++heap_size] = d;
    // greater<int>() 表示这是一个小根堆（最小的元素在前面）
    push_heap(heap+1, heap+heap_size+1, greater<int>()); 
}

---

2. 获取并删除堆顶元素（get 操作）

获取堆顶元素是最快的操作，因为堆顶就是数组的第一个元素 heap[1]。但删除后，我们必须重新调整堆，这个过程叫做**“下沉”（或“下滤”**）。

步骤（以小根堆为例）：

1. 记录下堆顶元素（要返回的结果）。
2. 将数组末尾的元素（即最后一个叶子节点）移到堆顶（heap[1]），并把堆的大小减 1。
3. 将这个新的堆顶元素和它的子节点进行比较。
4. 找到它的最小的那个子节点（如果是大根堆，则找最大）。
5. 如果这个新的堆顶元素比最小的子节点大（违反了小根堆性质），就和这个最小的子节点交换位置。
6. 重复第 3、4、5 步，直到它到达叶子节点或者它不再比子节点大为止（堆序性恢复）。

💡 代码示例（自定义小根堆删除）

您提供的自定义删除函数 get() 实现了这个“下沉”过程：

int get() // heap[1]为堆顶
{
    int now, next, res;
    res = heap[1]; // 1. 记录结果
    heap[1] = heap[heap_size--]; // 2. 最后一个元素移到堆顶，堆大小减 1
    now = 1;
    while (now * 2 <= heap_size) // 循环直到 now 已经没有左子节点
    {
        next = now * 2; // next 默认是左子节点
        // 4. 找出较小的子节点
        if (next < heap_size && heap[next + 1] < heap[next]) next++; 
        
        if (heap[now] <= heap[next]) break; // 5. 如果比最小的子节点小或相等，停止
        
        swap(heap[now], heap[next]); // 6. 交换
        now = next; // 继续往下沉
    }
    return res;
}

🛠️ C++ STL 标准库实现

pop_heap 函数会将堆顶元素（最小/最大的那个）移动到数组的最后一个有效位置，然后剩下的元素重新调整成堆。所以，我们需要在 pop_heap 后取出数组末尾的元素，并减小堆的大小。

// 小根堆的 STL 删除
int get()
{
    // pop_heap 将最小的元素放到 heap[heap_size] 的位置
    pop_heap(heap+1, heap+heap_size+1, greater<int>()); 
    // 返回并移除末尾的那个元素（原堆顶）
    return heap[heap_size--];
}

---

堆有什么用？

堆最常见的应用包括：

1. 优先队列（Priority Queue）： 堆是实现优先队列的最佳方式。优先队列总是确保你可以最快地拿到优先级最高（最大或最小）的那个元素。

   • 例如：医院里总是优先处理伤势最重的病人。

2. 堆排序（Heapsort）： 一种高效的排序算法，利用堆的特性将所有元素依次取出，从而得到一个有序的序列。

3. 图算法： 在著名的图算法，如 Dijkstra 算法和 Prim 算法中，堆被用来快速找到最短路径或最小生成树中的下一个节点。

记住： 堆的核心优势在于，无论是插入还是获取堆顶元素，其时间复杂度都非常高效，通常是 $O(\log n)$（对数时间）。