堆 | Wuhaoda's Blog

介绍:

具体介绍见:
https://www.luogu.org/blog/henry-y/qian-xi-ji-chu-shuo-ju-jie-gou-er-cha-dui
由于时间关系没有学习手打堆
但是学会了简单应用

使用:

手打堆:

这个坑以后再补

STL优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;

priority_queue< int, vector<int>, greater<int> > q;
int n, x;

int main() {
scanf("%d", &n);
for(register int i = 1; i <= n; ++i) {
scanf("%d", &x);
if(x == 1) {
scanf("%d", &x);
q.push(x);
}
else {
if(x == 2)
printf("%d\n", q.top());
else
q.pop();
}
}
}

编码难度最简单,貌似比STL heap慢一半
可以用重载运算符自定义规则

STL heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int heap_size;
int heap[1000005];

void put(int x) {
heap[++heap_size] = x;
push_heap(heap + 1, heap + 1 + heap_size, greater<int>());
}

int get() {
return heap[1];
}

void del() {
pop_heap(heap + 1, heap + 1 + heap_size, greater<int>());
--heap_size;
}

int main() {
int n, x;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
if(x == 1) {
scanf("%d", &x);
put(x);
}
else if(x == 2)
printf("%d\n", get());
else
del();
}
}