【堆】模拟堆「堆基础2」

题目

839. 模拟堆

---

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x，插入一个数 $x$；
2. PM，输出当前集合中的最小值；
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. D k，删除第 $k$ 个插入的数；
5. C k x，修改第 $k$ 个插入的数，将其变为 $x$；

现在要进行 $N$ 次操作，对于所有第 $2$ 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$
数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

解题

方法一：最小堆

思路

堆模版：堆

堆

接上文。

要做到删除或修改任一元素 k 需要知道第 k 个插入的元素是什么，所以不能只维护一个堆，还需要维护 ph 与 hp，ph[k] 表示第 k 个元素在数组中的下标，hp[] 则相反，表示堆里的某一个点是第几个插入的点，这两个数组在 up 或 down 操作做交换的时候会用到：

学会 heap_swap() 操作后把之前操作中的交换全部换成 heap_swap() 并在插入元素时维护 ph 、hp 映射数组即可。

代码

#include <iostream>
#include <limits>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int heap[N], hp[N], ph[N], idx;
int n, m;

void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(heap[a], heap[b]);
}

void down(int k) {
    int min = k;
    if (k * 2 <= idx && heap[k * 2] < heap[min]) min = k * 2;
    if (k * 2 + 1 <= idx && heap[k * 2 + 1] < heap[min]) min = k * 2 + 1;
    if (min != k) {
        heap_swap(k, min);
        down(min);
    }
}

void up(int k) {
    while (k / 2 && heap[k / 2] > heap[k]) {
        heap_swap(k, k / 2);
        k /= 2;
    }
}

int main() {
    scanf("%d", &n);
    while (n--) {
        char ope[2];
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        scanf("%s", ope);
        int k, x;
        if (ope[0] == 'I') {
            scanf("%d", &x);
            ph[++m] = ++idx;
            hp[idx] = m;
            heap[idx] = x;
            up(idx);
        } else if (!strcmp(ope, "PM")) printf("%d\n", heap[1]);
        else if (!strcmp(ope, "DM")) {
            heap_swap(1, idx--);
            down(1);
        } else if (ope[0] == 'D') {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, idx--);
            up(k);
            down(k);
        } else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            heap[k] = x;
            up(k);
            down(k);
        }
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) 1e5 + 10;
    static int[] h = new int[N], hp = new int[N], ph = new int[N];
    static int size;
    
    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    static void heap_swap(int a, int b) {
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
        swap(h, a, b);
    }
    
    static void down(int k) {
        int min = k;
        if (k * 2 <= size && h[k * 2] < h[min]) min = k * 2;
        if (k * 2 + 1 <= size && h[k * 2 + 1] < h[min]) min = k * 2 + 1;
        if (min != k) {
            heap_swap(k, min);
            down(min);
        }
    }
    
    static void up(int k) {
        while (k / 2 > 0 && h[k / 2] > h[k]) {
            heap_swap(k, k / 2);
            k /= 2;
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval, m = 0;
        while (n-- > 0) {
            in.nextToken();
            String ope = in.sval;
            if (ope.charAt(0) == 'I') {
                in.nextToken();
                int x = (int) in.nval;
                ph[++m] = ++size;
                hp[size] = m;
                h[size] = x;
                up(size);
            } else if (ope.charAt(0) == 'P') System.out.println(h[1]);
            else if (ope.equals("DM")) {
                heap_swap(1, size--);
                down(1);
            } else if (ope.charAt(0) == 'D') {
                in.nextToken();
                int k = (int) in.nval;
                k = ph[k];
                heap_swap(k, size--);
                up(k);
                down(k);
            } else {
                in.nextToken();
                int k = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                k = ph[k];
                h[k] = x;
                up(k);
                down(k);
            }
        }
    }
}