洛谷 P3378 【模板】堆

Description

• 如题，初始小根堆为空，我们需要支持以下3种操作：

  操作1： 1 x 表示将x插入到堆中

  操作2： 2 输出该小根堆内的最小数

  操作3： 3 删除该小根堆内的最小数

Input

• 第一行包含一个整数N，表示操作的个数

  接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：

  操作1： 1 x

  操作2： 2

  操作3： 3

Output

• 包含若干行正整数，每行依次对应一个操作2的结果。

Sample Input

51 21 5232

Sample Output

2

5

Data Size

• 对于30%的数据：N<=15

  对于70%的数据：N<=10000

  对于100%的数据：N<=1000000（注意是6个0。。。不过不要害怕，经过编者实测，堆是可以AC的）

题解：

• 二叉堆。
• 手写堆，STL也行。但STL做不到在堆中删除某一个结点。

1. Insert：向二叉堆中插入一个带有权值val的新节点。把这个新节点直接放在二叉堆的数组末尾，然后通过交换的方式向上调整，直到满足堆的性质。
2. GetTop：返回二叉堆堆顶权值，即heap[1]。
3. Remove：将存储在数组下标p位置的节点从二叉堆中删除。先将heap[p]与heap[n]交换，然后n–，这时heap[p]可能需要向上或向下进行调整，分别检查并处理。（注意，当p=1时，即删除堆顶时，只用向下调整）

#include 
    
     #include 
     
      #define N 1000005using namespace std;int n, tot;int heap[N];int read(){    int x = 0; char c = getchar();    while(c < '0' || c > '9') c = getchar();    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}    return x;}void up(int x){    while(x > 1)    {        if(heap[x] < heap[x / 2]) swap(heap[x], heap[x / 2]), x /= 2;        else break;    }}void down(int x){    while(x * 2 <= tot)    {        int y = x * 2;        if(y < tot && heap[y] > heap[y + 1]) y++;        if(heap[y] < heap[x]) swap(heap[y], heap[x]), x = y;        else break;    }}int main(){    cin >> n;    for(int i = 1; i <= n; i++)    {        int op = read();        if(op == 1) {heap[++tot] = read(), up(tot);}        else if(op == 2) printf("%d\n", heap[1]);        else if(op == 3) {heap[1] = heap[tot--]; down(1);}    }    return 0;}