-
Notifications
You must be signed in to change notification settings - Fork 12
/
heap.cpp
69 lines (58 loc) · 1.87 KB
/
heap.cpp
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//
// 二分ヒープの実装
//
#include <iostream>
#include <vector>
using namespace std;
struct Heap {
vector<int> heap;
Heap() {}
// ヒープに値 x を挿入
void push(int x) {
heap.push_back(x); // 最後尾に挿入
int i = (int)heap.size() - 1; // 挿入された頂点番号
while (i > 0) {
int p = (i - 1) / 2; // 親の頂点番号
if (heap[p] >= x) break; // 逆転がなければ終了
heap[i] = heap[p]; // 自分の値を親の値にする
i = p; // 自分は上に行く
}
heap[i] = x; // x は最終的にはこの位置にもってくる
}
// 最大値を知る
int top() {
if (!heap.empty()) return heap[0];
else return -1;
}
// 最大値を削除
void pop() {
if (heap.empty()) return;
int x = heap.back(); // 頂点にもってくる値
heap.pop_back();
int i = 0; // 根から降ろしていく
while (i * 2 + 1 < (int)heap.size()) {
// 子頂点同士を比較して大きい方を child1 とする
int child1 = i * 2 + 1, child2 = i * 2 + 2;
if (child2 < (int)heap.size()
&& heap[child2] > heap[child1]) {
child1 = child2;
}
if (heap[child1] <= x) break; // 逆転がなければ終了
heap[i] = heap[child1]; // 自分の値を子頂点の値にする
i = child1; // 自分は下に行く
}
heap[i] = x; // x は最終的にはこの位置にもってくる
}
};
//------------------------------//
// Examples
//------------------------------//
int main() {
Heap h;
h.push(5), h.push(3), h.push(7), h.push(1);
cout << h.top() << endl; // 7
h.pop();
cout << h.top() << endl; // 5
h.push(11);
cout << h.top() << endl; // 11
}