模拟堆
语义化了api,将操作封装成函数,更好理解了一些
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int heap[N], heap_size;
// is2hi和hi2is 存放的是插入顺序与堆下标的映射
// is2hi: insert sequence -> heap index,2即是to(谐音)
// hi2is: heap index -> insert index
int is2hi[N], hi2is[N];
int sequence;
void heap_swap(int a, int b) {
swap(is2hi[hi2is[a]], is2hi[hi2is[b]]);
swap(hi2is[a], hi2is[b]);
swap(heap[a], heap[b]);
}
void down(int index) {
int min_index = index;
if (index * 2 <= heap_size && heap[index * 2] < heap[min_index]) min_index = index * 2;
if (index * 2 + 1 <= heap_size && heap[index * 2 + 1] < heap[min_index]) min_index = index * 2 + 1;
if (min_index != index) {
heap_swap(index, min_index);
down(min_index);
}
}
void up(int index) {
while (index / 2 && heap[index] < heap[index / 2]) {
heap_swap(index, index / 2);
index >>= 1;
}
}
int top() {
return heap[1];
}
void insert(int value) {
heap_size++;
sequence++;
is2hi[sequence] = heap_size, hi2is[heap_size] = sequence;
heap[heap_size] = value;
up(heap_size);
}
void remove_top() {
heap_swap(1, heap_size);
heap_size--;
down(1);
}
void remove_nth(int insert_sequence) {
int heap_index = is2hi[insert_sequence];
heap_swap(heap_index, heap_size);
heap_size--;
up(heap_index), down(heap_index);
}
void update_nth(int insert_sequence, int value) {
int heap_index = is2hi[insert_sequence];
heap[heap_index] = value;
up(heap_index), down(heap_index);
}
/**
* acwing 839-模拟堆
* @return
*/
int main() {
int n;
cin >> n;
string op;
int k, x;
while (n--) {
cin >> op;
if (op == "I") {
cin >> x;
insert(x);
} else if (op == "PM") {
cout << top() << endl;
} else if (op == "DM") {
remove_top();
} else if (op == "D") {
cin >> k;
remove_nth(k);
} else if (op == "C") {
cin >> k >> x;
update_nth(k, x);
}
}
return 0;
}