-
Notifications
You must be signed in to change notification settings - Fork 1
/
RandomizedHeap.cpp
71 lines (53 loc) · 1.51 KB
/
RandomizedHeap.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
#include <bits/stdc++.h>
using namespace std;
mt19937 rd(10);
uniform_int_distribution<int> toss(0, 1);
// randomized heap https://cp-algorithms.com/data_structures/randomized_heap.html
// capable of O(log n) insertion, pop_min, melding (combining two heaps)
// and O(1) get_min
template<typename T>
struct RandomizedHeap {
using ptr = unique_ptr<RandomizedHeap<T>>;
T val;
ptr l, r;
RandomizedHeap() = default;
RandomizedHeap(T x) : val(x), l(nullptr), r(nullptr) {};
// combines two heaps a and b
// consumes heap a and b, and procudes a new heap
friend auto meld(ptr a, ptr b) -> ptr {
if (!a) return b;
if (!b) return a;
// a is the root
if (a->val > b->val) swap(a, b);
// 50/50 chance to combine b with each child of a
if (toss(rd)) a->l = meld(move(a->l), move(b));
else a->r = meld(move(a->r), move(b));
return a;
}
friend auto insert(ptr& a, T x) -> void {
a = meld(move(a), make_unique<RandomizedHeap>(x));
}
friend auto pop(ptr& a) -> void {
a = meld(move(a->l), move(a->r));
}
auto min() -> T {
return val;
}
};
int main() {
RandomizedHeap<int>::ptr a, b;
for (int i = 0; i < 10; i += 2) {
insert(a, i);
insert(b, i+1);
}
cout << a->min() << '\n';
cout << b->min() << '\n';
pop(a), pop(a);
pop(b);
auto c = meld(move(a), move(b));
while (c) {
cout << c->min() << ' ';
pop(c);
}
cout << '\n';
}