题目描述

就是对一个堆的增删改查。
“I x”，插入一个数x；
“PM”，输出当前集合中的最小值；
“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
“D k”，删除第k个插入的数；
“C k x”，修改第k个插入的数，将其变为x；

输入样例

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

输出样例

-10
6

模板部分 ***

// 普通交换
static void swap(int[] abc, int a, int b){
    int t = abc[a];
    abc[a] = abc[b];
    abc[b] = t;
}
// 堆交换
static void head_swap(int a, int b){
    swap(h, a, b);// 交换值
    swap(hp, a, b);// 交换hp指向的ph
    swap(ph, hp[a], hp[b]);// 交换ph
}
// down up 就是维护小顶堆的
// 向下移动
static void down(int u){
    int t = u;
    if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u;// t > 左子树
    if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1;// t < 右子树
    if (u != t){
        head_swap(u, t);
        down(t);
    }
}
// 向上移动
static void up(int u){
    while (u / 2 != 0 && h[u / 2] > h[u]){// u < u对应的根节点
        head_swap(u, u / 2);
        u /= 2;
    }
}

算法1

(堆) $O(nlog(n))$

“I x”，插入一个数x；
    在结尾拆入一个数，然后维护一下堆（up）
“PM”，输出当前集合中的最小值；
    输出h[1]
“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
    将堆中最后一个值和堆顶交换，删除堆尾然后down一下
“D k”，删除第k个插入的数；
    找到第k个，然后和堆尾交换一下，删除队尾，然后down+up
“C k x”，修改第k个插入的数，将其变为x；
    找到第k个，然后改值

时间复杂度：$O(nlog(n))$

参考文献：y总

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] h = new int[N];// 存放堆元素 从1开始
    static int[] ph = new int[N];// 存放下标k 从1开始
    static int[] hp = new int[N];// 存放下标k对那个的ph的下标
    static int size = 0;
    // 普通交换
    static void swap(int[] abc, int a, int b){
        int t = abc[a];
        abc[a] = abc[b];
        abc[b] = t;
    }
    // 堆交换
    static void head_swap(int a, int b){
        swap(h, a, b);// 交换值
        swap(hp, a, b);// 交换hp指向的ph
        swap(ph, hp[a], hp[b]);// 交换ph
    }
    // down up 就是维护小顶堆的
    // 向下移动
    static void down(int u){
        int t = u;
        if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u;// t > 左子树
        if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1;// t < 右子树
        if (u != t){
            head_swap(u, t);
            down(t);
        }
    }
    // 向上移动
    static void up(int u){
        while (u / 2 != 0 && h[u / 2] > h[u]){// u < u对应的根节点
            head_swap(u, u / 2);
            u /= 2;
        }
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        int m = 0;
        while (n-- > 0){
            String[] s = scan.nextLine().split(" ");
            int k = 0,x = 0;
            if ("I".equals(s[0])){// 拆入
                x = Integer.parseInt(s[1]);
                m++;
                size++;
                h[size] = x;
                ph[m] = size;// 记录k
                hp[size] = m;// 通过size找到ph 从而找到k
                up(size);
            }else if ("PM".equals(s[0])){// 输出栈顶
                System.out.println(h[1]);
            }else if ("DM".equals(s[0])){// 删除栈顶
                // 将最后一个元素 放到第一个 然后down
                head_swap(1, size);
                size--;
                down(1);
            }else if ("C".equals(s[0])){// 在第k个元素上修改值
                // 找到第k个插入的元素 该值 down up以下
                k = Integer.parseInt(s[1]);
                x = Integer.parseInt(s[2]);
                k = ph[k];// 找到第k个元素
                h[k] = x;
                down(k);
                up(k);
            }else if ("D".equals(s[0])){
                // 找到k对应的值 然后和size交换 删除size 最后down up
                k = Integer.parseInt(s[1]);
                k = ph[k];
                head_swap(k, size);
                size--;
                down(k);
                up(k);
            }

        }
    }
}