堆（Heap）是一种完全二叉树，通常用于实现优先队列，支持高效的插入、删除、取最大/最小值操作。堆分为 最大堆（Max Heap） 和 最小堆（Min Heap），两者的区别在于父节点与子节点的关系：

  • 最大堆：父节点的值 ≥ 子节点的值，根节点是整个堆中的最大值。
  • 最小堆：父节点的值 ≤ 子节点的值，根节点是整个堆中的最小值。

堆主要通过 数组 进行存储，并使用 二叉树的性质 进行索引。

1. 堆的数组存储结构

堆是一棵完全二叉树，所以可以直接使用数组存储，而不需要额外的指针。对于数组 arr[] 中的元素，索引从 0 或 1 开始 存储，假设父节点索引为 i，那么：

  • 左子节点：arr[2*i + 1] （从 0 开始）或 arr[2*i]（从 1 开始）
  • 右子节点：arr[2*i + 2] （从 0 开始）或 arr[2*i + 1]（从 1 开始）
  • 父节点：arr[(i-1)/2]（从 0 开始）或 arr[i/2]（从 1 开始）

示例：最大堆存储示意（索引从 0 开始）

        16
       /  \
     14    10
    /  \   /  \
   8   7  9   3
  / \
 2   4

数组表示：[16, 14, 10, 8, 7, 9, 3, 2, 4]
arr[0] = 16, arr[1] = 14, arr[2] = 10, arr[3] = 8, arr[4] = 7 ...

2. 堆的基本操作

堆的核心操作包括 插入、删除、堆化（heapify） 等。

2.1 插入元素

插入新元素到堆的最后一个位置，然后向上调整（上浮操作）：

  1. 先把元素放在数组末尾 arr[n]。
  2. 如果新元素比父节点大（最大堆）或小（最小堆），则交换它们。
  3. 继续向上调整，直到满足堆的性质。

代码示例（PHP）

function heapInsert(&$heap, $value) {
    $heap[] = $value; // 先插入到最后
    $i = count($heap) - 1; 

    while ($i > 0) {
        $parent = floor(($i - 1) / 2);
        if ($heap[$parent] >= $heap[$i]) break; // 最大堆条件：父 ≥ 子

        swap($heap, $i, $parent);
        $i = $parent;
    }
}

function swap(&$arr, $i, $j) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

2.2 删除堆顶元素

删除堆顶元素（通常是最大值/最小值）后，需要下沉调整：

  1. 用最后一个元素替换堆顶元素。
  2. 比较父节点与两个子节点，交换较大（或较小）的子节点，使其满足堆性质。
  3. 继续向下调整，直到叶子节点。

代码示例（PHP）

function heapDelete(&$heap) {
    $n = count($heap);
    if ($n == 0) return null;

    $maxValue = $heap[0]; // 取出堆顶
    $heap[0] = array_pop($heap); // 用最后一个元素替换堆顶
    heapify($heap, 0);
    
    return $maxValue;
}

function heapify(&$heap, $i) {
    $n = count($heap);
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $n && $heap[$left] > $heap[$largest]) {
        $largest = $left;
    }
    if ($right < $n && $heap[$right] > $heap[$largest]) {
        $largest = $right;
    }
    
    if ($largest != $i) {
        swap($heap, $i, $largest);
        heapify($heap, $largest);
    }
}

3. 堆的构建

堆的构建可以通过多次插入 或 自底向上的 Heapify 来完成。

3.1 直接插入建堆

从空堆开始，逐个插入元素并进行上浮，时间复杂度 O(n log n)。

3.2 自底向上建堆

从倒数第二层开始，逐层向上进行 Heapify，时间复杂度 O(n)。

代码示例（PHP）

function buildHeap(&$arr) {
    $n = count($arr);
    for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $i);
    }
}

4. 堆排序

堆排序基于最大堆：

  1. 先建堆（O(n)）。
  2. 依次取出堆顶元素（最大值），并调整堆（O(log n)）。
  3. 时间复杂度 O(n log n)。

代码示例（PHP）

function heapSort(&$arr) {
    buildHeap($arr);
    $n = count($arr);
    
    for ($i = $n - 1; $i > 0; $i--) {
        swap($arr, 0, $i); // 交换堆顶和最后一个元素
        heapify($arr, 0, $i);
    }
}

function heapify(&$arr, $i, $n) {
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $n && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $n && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }
    
    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $largest, $n);
    }
}

5. 常见应用

  1. 优先队列（Priority Queue）
    • 操作系统进程调度（最高优先级任务先执行）
    • Dijkstra 最短路径算法
  2. Top K 问题（如找前 10 大的数）
    • 使用最小堆，时间复杂度 O(n log k)
  3. 区间最值查询（RMQ）
    • 维护滑动窗口最大值
  4. 实时数据流分析
    • 使用堆维护中位数，时间复杂度 O(log n)

总结

  • 堆是一棵完全二叉树，适合用数组存储。
  • 主要操作：插入（上浮）、删除（下沉）、建堆（Heapify）。
  • 堆排序是一种基于堆的 O(n log n) 排序方法。
  • 应用场景广泛：优先队列、Top K 问题、最短路径、实时数据处理等。

堆在算法竞赛和工程实践中都极为重要，建议多加练习！🚀