AcWing 839. 模拟堆
原题链接
简单
作者:
gongjin
,
2023-01-03 15:09:50
,
所有人可见
,
阅读 116
数据模拟堆 JAVA实现
import java.util.Scanner;
class Main {
static int N = 100010;
static int[] h = new int[N];
static int[] ph = new int[N];
static int[] hp = new int[N];
static int size;
static int m;
public static void down(int u) {
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) {
heap_swap(u, t);
down(t);
}
}
public static void up(int u) {
while (u / 2 > 0 && h[u] < h[u / 2]) {
heap_swap(u, u / 2);
u /= 2;
}
}
//节点编号
public static void heap_swap(int a, int b) {
int tmp = ph[hp[a]];
ph[hp[a]] = ph[hp[b]];
ph[hp[b]] = tmp;
tmp = hp[a];
hp[a] = hp[b];
hp[b] = tmp;
tmp = h[a];
h[a] = h[b];
h[b] = tmp;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < n; i++) {
String op = scanner.next();
if (op.equals("I")) {
int x = Integer.parseInt(scanner.next());
m++;
size++;
h[size] = x;
ph[m] = size;
hp[size] = m;
up(size);
} else if (op.equals("PM")) {
System.out.println(h[1]);
} else if (op.equals("DM")) {
heap_swap(1, size);
size--;
down(1);
} else if (op.equals("D")) {
int k = Integer.parseInt(scanner.next());
k = ph[k];
heap_swap(k, size);
size--;
down(k);
up(k);
} else {
int k = Integer.parseInt(scanner.next());
int x = Integer.parseInt(scanner.next());
k = ph[k];
h[k] = x;
down(k);
up(k);
}
}
}
}