AcWing 839. 模拟堆_java实现含注释
原题链接
简单
作者:
FayunYm
,
2020-12-27 12:00:42
,
所有人可见
,
阅读 382
import java.io.*;
public class Heap2 {
static final int N =100_010;
static int[] h = new int[N];
static int size;
static int[] ph = new int[N]; //ph[k]表示第k个插入的元素当前在ph[k]处
static int[] hp = new int[N]; //hp[k]表示当前k坐标所在元素是第hp[k]个插入的
static int total; //插入几个了
static void swap(int i, int t) {
//交换两值后,对应的hp值应该交换
ph[hp[i]] = t;
ph[hp[t]] = i;
//交换这两个坐标处值的插入顺序
int temp = hp[i];
hp[i] = hp[t];
hp[t] = temp;
temp = h[i];
h[i] = h[t];
h[t] = temp;
}
static void down(int i) {
int t = i; //t用于存放3个元素中最小值所在位置
if(i*2 <= size && h[i*2] < h[t]) t = i*2;
if(i*2+1 <= size && h[i*2+1] < h[t]) t = i*2+1;
if(i != t) { //若已到底或当前结点就是最小值,则不执行
swap(i,t);
down(t);
}
}
static void up(int i) {
while(i/2 != 0 && h[i] < h[i/2]) {
swap(i,i/2);
i /=2;
}
}
static void insert(int x) {
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
String s = reader.readLine();
int n = Integer.parseInt(s);
while(n-- != 0) {
String[] op = reader.readLine().split(" ");
if(op[0].equals("I")) {
int x = Integer.parseInt(op[1]);
size ++;
total ++;
ph[total] = size;
hp[size] = total;
h[size] = x;
up(size);
} else if (op[0].equals("PM")) {
log.write(h[1]+"\n");
} else if(op[0].equals("DM")) {
swap(1,size);
size--;
down(1);
} else if (op[0].equals("D")) {
int k = Integer.parseInt(op[1]);
k = ph[k];
swap(k,size);
size--;
down(k); //up down只执行一个
up(k);
} else {
int k = Integer.parseInt(op[1]);
int x = Integer.parseInt(op[2]);
k = ph[k];
h[k] = x;
down(k);
up(k);
}
}
log.flush();
log.close();
reader.close();
}
}