堆(heap)
在 set 的章節中我們學過，set 可以隨時維護一個排序好的集合。但這相當難以實作，並且雖然複雜度是 $O(logN)$，但有著較大的常數。
如果，我不需要那麼多功能，只需要支援：加入一個元素、查詢最大元素、刪除最大元素這幾個操作，其實有個比較快的方法：heap
heap 介紹
查詢最大值
直接回傳 1 號節點數字。
刪除最大值
將 N 號移到 1 號位置，接著不停與其兒子比較，將其與較大的兒子交換，直到其無法再交換為止。
插入值
將新的值加入 N+1 號位置，不停與其父親比較，直到其值小於父親為止。
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
| int heap[1000005], N = 0;
int mx(){
return heap[1];
}
void del(){
assert(N > 0);
heap[1] = heap[N];
N--;
for(int i=1,to;i*2<=N;i=to){
if(i*2+1 > N || heap[i*2] > heap[i*2+1]) to = i*2;
else to = i*2+1;
if(heap[i] > heap[to]) break;
swap(heap[i], heap[to]);
}
}
void ins(int x){
N++;
heap[N] = x;
for(int i=N;i>1;i>>=1){
if(heap[i/2] > heap[i]) break;
swap(heap[i/2], heap[i]);
}
}
|
而在 STL 中，有個名為 priority_queue 的結構，其內部便是以 heap 實作。它能夠做到 $O(1)$ 查詢最大值、$O(logN)$ 加入元素、$O(logN)$ 刪除最大值。
由於功能完全是 set 的子集，set 能任意刪而 priority_queue 只能刪除最大值，因此大多數時候使用 set，只有在 set 被卡時間以及特定演算法上會使用到 priority_queue。
priority_queue
宣告
加入元素
查詢最大
1
| cout << pq.top() << '\n';
|
刪除最大
更改比較函式
與 set 不同的是，priority_queue 其實有三個參數，分別為型態、底層容器、以及比較函式。若不需更改比較函式，宣告時只需第一參數即可，但若需要自訂比較函式，則需三個都寫出來：
1
| priority_queue<int, vector<int>, greater<int>> pq;
|
另一個比較反直覺的東西，則是排在 priority_queue 頂的元素，其實是跟比較函式相反的。例如說，預設的 less<> 函式，排在最上方的反而是最大的元素。若要得到最小的元素，則須使用 greater<> 比較函式。
例題
把之前 set 題裡的拿來用
TIOJ 1161
★★★★TIOJ 1231
AC Code
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
|
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
priority_queue<int> pq;
int n, k;
pii arr[1000005];
void solve(){
while(!pq.empty()) pq.pop();
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> arr[i].first >> arr[i].second;
sort(arr+1, arr+n+1);
int ans = 1e9;
for(int i=1;i<=n;i++){
pq.push(arr[i].second);
if(pq.size() > k) pq.pop();
if(pq.size() == k) ans = min(ans, arr[i].first + pq.top());
}
cout << ans << '\n';
}
int main(){
int t; cin >> t; while(t--) solve();
}
|
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
38
39
40
41
42
43
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
priority_queue<ll> pq;
pii arr[100005];
int n, k;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i].second >> arr[i].first;
sort(arr+1, arr+1+n, greater<pii>());
cin >> k;
ll t = k, idx = 1, ans = 0;
priority_queue<int> pq;
while(t > 0){
while(idx <= n && arr[idx].first >= t){
pq.push(arr[idx].second);
idx++;
}
if(pq.empty()){
ans -= t - arr[idx].first;
t = arr[idx].first;
}
else{
ans += pq.top();
pq.pop();
t--;
}
}
cout << ans << '\n';
}
|