AcWing 838. 堆排序 原题链接
输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数，表示整数数列。
输出格式
共一行，包含m个整数，表示整数数列中前m小的数。
数据范围
1≤m≤n≤1051≤m≤n≤105， 1≤数列中元素≤1091≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
class Heap{
int[] heap;
int size;
public void creatHeapByArray(int n, int[] arr) {
heap = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
heap[i] = arr[i - 1];
}
size = n;
for (int i = n / 2; i >= 1; i--) {
down(i);
}
}
public void up(int idx) {
while (idx / 2 >= 1 && heap[idx / 2] > heap[idx]) {
int temp = heap[idx / 2];
heap[idx / 2] = heap[idx];
heap[idx] = temp;
idx /= 2;
}
}
public void down(int idx) {
int left = idx * 2;
int right = idx * 2 + 1;
int t = idx;
if (left <= size && heap[left] < heap[t]) {
t = left;
}
if (right <= size && heap[right] < heap[t]) {
t = right;
}
if (idx == t) {
return;
}
int temp = heap[idx];
heap[idx] = heap[t];
heap[t] = temp;
down(t);
}
public int poll() {
int t = heap[1];
heap[1] = heap[size];
size--;
down(1);
return t;
}
}
AcWing 839. 模拟堆 原题链接
维护一个集合，初始时集合为空，支持如下几种操作：
- “I x”，插入一个数x；
- “PM”，输出当前集合中的最小值；
- “DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
- “D k”，删除第k个插入的数；
- “C k x”，修改第k个插入的数，将其变为x；
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。
输入格式
第一行包含整数N。
接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。
输出格式
对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤1051≤N≤105 −109≤x≤109−109≤x≤109 数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
使用自定义堆的好处
- 可以删除堆中任意位置的数
- 可以与原数组做一一映射
用的不多，就不定义新的数据结构了
public class Main {
static final MyScanner in = new MyScanner();
static final MyWriter myOut = new MyWriter();
static final PrintWriter out = myOut.out;
static int[] heap;
static int size;
static int[] hp;
static int[] ph;
static int idx;
private static void heapSwap(int i, int j) {
MyOptions.swap(ph, hp[i], hp[j]);
MyOptions.swap(hp, i, j);
MyOptions.swap(heap, i, j);
}
private static void down(int idx) {
int t = idx;
int left = idx * 2;
int right = idx * 2 + 1;
if (left <= size && heap[left] < heap[t]) {
t = left;
}
if (right <= size && heap[right] < heap[t]) {
t = right;
}
if (t == idx) {
return;
}
heapSwap(t, idx);
down(t);
}
private static void up(int idx) {
while (idx / 2 >= 1 && heap[idx / 2] > heap[idx]) {
heapSwap(idx / 2, idx);
idx /= 2;
}
}
private static void insert(int val) {
heap[++size] = val;
ph[++idx] = size;
hp[size] = idx;
up(size);
}
private static void deleteMin() {
heapSwap(1, size);
size--;
down(1);
}
private static void deleteK(int k) {
int t = ph[k];
heapSwap(t, size);
size--;
down(t);
up(t);
}
private static void changeK(int k, int val) {
int t = ph[k];
heap[t] = val;
down(t);
up(t);
}
public static void main(String[] args) {
int n = in.nextInt();
heap = new int[n + 1];
hp = new int[n + 1];
ph = new int[n + 1];
while (n-- > 0) {
String str = in.nextLine();
String[] ss = str.split(" ");
if ("I".equals(ss[0])) {
insert(Integer.parseInt(ss[1]));
} else if ("PM".equals(ss[0])) {
out.println(heap[1]);
} else if ("DM".equals(ss[0])) {
deleteMin();
} else if ("D".equals(ss[0])) {
deleteK(Integer.parseInt(ss[1]));
} else if ("C".equals(ss[0])) {
changeK(Integer.parseInt(ss[1]), Integer.parseInt(ss[2]));
}
}
out.flush();
out.close();
}