-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap.cpp
86 lines (73 loc) · 1.84 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int> &vec, int size, int i) {
while (2 * i + 1 < size) {
int max_child = 2 * i + 1;
if (2 * i + 2 < size && vec[2 * i + 2] > vec[2 * i + 1])
max_child = 2 * i + 2;
if (vec[max_child] > vec[i]) {
swap(vec[i], vec[max_child]);
i = max_child;
} else {
return;
}
}
}
void heapify(vector<int> &vec, int i) { heapify(vec, vec.size(), i); }
void makeHeap(vector<int> &vec) {
auto size = vec.size();
for (int i = (size - 2) / 2; i >= 0; --i) {
heapify(vec, i);
}
}
void bubbleUp(vector<int> &vec, int i) {
while ((i - 1) / 2 >= 0 && vec[i] > vec[(i - 1) / 2]) {
swap(vec[i], vec[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void pushHeap(vector<int> &vec, int e) {
vec.push_back(e);
bubbleUp(vec, vec.size() - 1);
}
int popHeap(vector<int> &vec, int size) {
int e = vec[0];
swap(vec[0], vec[size - 1]);
// vec.pop_back();
heapify(vec, size - 1, 0);
return e;
}
int popHeap(vector<int> &vec) { return popHeap(vec, vec.size()); }
void heapSort(vector<int> &heap) {
for (int i = 0; i < heap.size(); ++i) {
popHeap(heap, heap.size() - i);
}
}
ostream &operator<<(ostream &os, const vector<int> &vec) {
os << "[";
for (auto e : vec)
os << e << ", ";
os << "\b\b]";
return os;
}
vector<int> naiveMakeHeap(const vector<int> &vec) {
vector<int> vec2;
for (int i = 0; i < vec.size(); ++i) {
pushHeap(vec2, vec[i]);
}
return vec2;
}
int main() {
vector<int> vec{1, 10, 100};
vector<int> vec2 = naiveMakeHeap(vec);
make_heap(vec.begin(), vec.end());
/* push_heap(vec.begin(), vec.end()); */
// sort_heap(vec.begin(), vec.end());
cout << "std::make_heap: " << vec << '\n';
// makeHeap(vec2);
// heapSort(vec2);
cout << "makeHeap: " << vec2 << '\n';
return 0;
}