题解：P3378 【模板】堆

safdasdfsadfsdaf · 2025-04-19 11:11:10 · 题解

题解：【模板】堆

题目描述

给定一个数列，初始为空，请支持以下三种操作：

插入操作（op=1）：将整数 x 插入到数列中。
查询最小值（op=2）：输出数列中的最小值。
删除最小值（op=3）：删除数列中的最小值。如果有多个最小值，只删除一个；如果数列为空，输出 -1。

数据范围：操作次数 n \leq 10^6 ，输入整数 x < 2^{31} 。

解题思路

核心思想：使用二叉堆实现优先队列

本题可以使用小端堆（即堆顶元素为最小值的二叉堆）来高效实现插入、查询和删除操作。以下是具体实现细节。

数据结构：数组模拟二叉堆

完全二叉树性质：堆是一棵完全二叉树，可以用数组模拟存储。
父子节点关系：
- 父节点编号： x/2
- 左儿子编号： x \times 2
- 右儿子编号： x \times 2 + 1

核心操作

1. 插入操作（`push`）

插入时，将新元素添加到堆的末尾，并通过自下而上的修复（modify）维护堆的性质。

void modify(int x) {
    if (x == 1 || w[x] > w[x / 2]) return; // 如果满足小端堆性质，退出递归
    swap(w[x], w[x / 2]);                  // 否则交换当前节点与父节点
    modify(x / 2);                         // 继续修复父节点
}

void push(int x) {
    w[++tot] = x; // 将新元素插入堆尾
    modify(tot);  // 自下而上修复
}

2.查询最小值（`top`）

堆顶元素即为最小值，直接返回堆顶即可。如果堆为空，则不进行操作。

int top() {
    if (tot) return w[1]; // 堆非空时返回堆顶元素
}

3.删除最小值（`pop`）

删除时，将堆顶元素与堆尾元素交换后删除堆尾，并通过自上而下的修复（repair）维护堆的性质。如果堆为空，输出 -1。

void repair(int x) {
    if (x * 2 > tot) return; // 如果没有子节点，退出递归
    int tar = x * 2;         // 默认左儿子为目标节点
    if (x * 2 + 1 <= tot && w[x * 2 + 1] < w[x * 2]) tar = x * 2 + 1; // 找到更小的儿子
    swap(w[x], w[tar]);      // 交换当前节点与目标节点
    repair(tar);             // 继续修复目标节点
}

void pop() {
    if (tot) {
        swap(w[1], w[tot--]); // 将堆顶与堆尾交换并删除堆尾
        repair(1);            // 自上而下修复
    } else printf("-1\n");    // 如果堆为空，输出 -1
}

复杂度分析

插入操作（push）：
- 每次插入一个新元素后，需要通过 modify 函数自下而上修复堆的性质。
- 修复过程中最多涉及 \log n 层（堆的高度为 \log n ），因此时间复杂度为 O(\log n) 。
查询最小值（top）：
- 查询堆顶元素时，直接返回数组的第一个元素，无需额外操作。
- 时间复杂度为 O(1) 。
删除最小值（pop）：
- 删除堆顶元素后，需要将堆尾元素移动到堆顶，并通过 repair 函数自上而下修复堆的性质。
- 修复过程中最多涉及 \log n 层，因此时间复杂度为 O(\log n) 。
总体复杂度：
- 假设总共有 n 次操作，每次操作的时间复杂度为 O( \log n) 。
- 因此，所有操作的总时间复杂度为 O(n \log n) 。

空间复杂度

使用一个数组 w 存储堆，数组大小为 n+1 （从下标 1 开始存储）。
空间复杂度为 O(n) 。