Heap类
template <typename Compare>
class Heap {
public:
explicit Heap(int capacity = 16) : compare(Compare()) {
numVec.reserve(capacity);
kToHeapVec.reserve(capacity);
heapToKVec.reserve(capacity);
}
// 堆中的元素个数, 时复O(1)
inline int size() const { return numVec.size(); }
// 堆是否为空, 时复O(1)
inline bool empty() const { return size(); }
// 获取堆顶的元素, 时复O(1)
inline int top() const { return numVec[0]; }
// 插入堆一个元素, 时复O(log(n))
void pushHeap(int num) {
const int index = size();
numVec.push_back(num);
if (static_cast<int>(heapToKVec.size()) <= index) {
if (static_cast<int>(heapToKVec.capacity()) <= index) {
const int newCapacity = max(static_cast<int>(heapToKVec.capacity()) << 1, index + 1);
heapToKVec.reserve(newCapacity);
}
heapToKVec.resize(index + 1);
}
heapToKVec[index] = kToHeapVec.size();
kToHeapVec.push_back(index);
up(index);
}
// 弹出堆顶元素, 时复O(log(n))
void popHeap() {
swapNum(0, size() - 1);
numVec.pop_back();
down(0);
}
// 删除第k个插入的数, 时复O(log(n))
void erase(int k) {
const int i = kToHeapVec[k];
swapNum(i, size() - 1);
numVec.pop_back();
up(i);
down(i);
}
// 修改第k个插入的数, 时复O(log(n))
void set(int k, int num) {
const int i = kToHeapVec[k];
numVec[i] = num;
up(i);
down(i);
}
private:
void up(int i) {
while (i) {
int parent = (i - 1) >> 1;
if (!compare(numVec[i], numVec[parent])) {
break;
}
swapNum(i, parent);
i = parent;
}
}
void down(int i) {
const int n = size();
for (;;) {
int j = i;
const int left = (i << 1) + 1;
if (left < n && compare(numVec[left], numVec[j])) {
j = left;
}
const int right = (i << 1) + 2;
if (right < n && compare(numVec[right], numVec[j])) {
j = right;
}
if (i == j) {
break;
}
swapNum(i, j);
i = j;
}
}
void swapNum(int i, int j) {
swap(kToHeapVec[heapToKVec[i]], kToHeapVec[heapToKVec[j]]);
swap(heapToKVec[i], heapToKVec[j]);
swap(numVec[i], numVec[j]);
}
const Compare compare;
vector<int> numVec;
vector<int> kToHeapVec;
vector<int> heapToKVec;
};
main函数
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n, k, x;
char oper[4];
scanf("%d", &n);
Heap<less<int>> heap(64);
for (int i = 0; i < n; ++i) {
scanf("%2s", oper);
if (!strcmp("I", oper)) {
scanf("%d", &x);
heap.pushHeap(x);
} else if (!strcmp("PM", oper)) {
printf("%d\n", heap.top());
} else if (!strcmp("DM", oper)) {
heap.popHeap();
} else if (!strcmp("D", oper)) {
scanf("%d", &k);
heap.erase(k - 1);
} else if (!strcmp("C", oper)) {
scanf("%d%d", &k, &x);
heap.set(k - 1, x);
}
}
return 0;
}
good