forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpersistent_heap.cc
More file actions
78 lines (71 loc) · 1.67 KB
/
persistent_heap.cc
File metadata and controls
78 lines (71 loc) · 1.67 KB
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
//
// Persistent Heap (based on randomized meldable heap)
//
// Description:
// Meldable heap with O(1) copy.
//
// Algorithm:
// It is a persistence version of randomized meldable heap.
//
// Complexity:
// O(log n) time/space for each operations.
//
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <map>
#include <cmath>
#include <cstring>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
template <class T>
struct persistent_heap {
struct node {
T x;
node *l, *r;
} *root;
persistent_heap() : root(0) { }
node *merge(node *a, node *b) {
if (!a || !b) return a ? a : b;
if (a->x > b->x) swap(a, b);
if (rand() % 2) return new node({a->x, merge(a->l, b), a->r});
else return new node({a->x, a->l, merge(a->r, b)});
}
void merge(persistent_heap b) { root = merge(root, b.root); }
void push(T x) { root = merge(root, new node({x})); }
void pop() { root = merge(root->l, root->r); }
T top() const { return root->x; }
};
int main() {
priority_queue<int, vector<int>, greater<int>> que;
persistent_heap<int> heap;
int n = 10000;
for (int i = 0; i < n; ++i) {
int x = rand();
heap.push(x);
que.push(x);
}
auto tmp_que = que;
auto tmp_heap = heap;
while (!que.empty()) {
if (heap.top() != que.top()) cout << "***" << endl;
que.pop();
heap.pop();
}
heap = tmp_heap;
que = tmp_que;
while (!que.empty()) {
if (heap.top() != que.top()) cout << "***" << endl;
que.pop();
heap.pop();
}
}