侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-10 / 0 评论 / 0 点赞 / 623 阅读 / 1,032 字
温馨提示:
本文最后更新于 2022-11-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

839. 模拟堆


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

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

现在要进行 NN 次操作,对于所有第 22 个操作,输出当前集合的最小值。

输入格式

第一行包含整数 NN

接下来 NN 行,每行包含一个操作指令,操作指令为 I xPMDMD kC k x 中的一种。

输出格式

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

每个结果占一行。

数据范围

1N1051 \le N \le 10^5
109x109-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 个插入的元素是什么,所以不能只维护一个堆,还需要维护 phhpph[k] 表示第 k 个元素在数组中的下标,hp[] 则相反,表示堆里的某一个点是第几个插入的点,这两个数组在 updown 操作做交换的时候会用到:heap-swap

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

代码

#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);
            }
        }
    }
}
0

评论区