CFTemplate/fibheap.cpp at master · EntropyIncreaser/CFTemplate · GitHub

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>

#include <algorithm>
#include <functional>
#include <queue>

using namespace std;

const int N;

template <class T, class Compare = less<T> >
struct FibHeap {
	struct Node {
		T k;
		int deg;
		bool mark;
		Node *prv, *nxt, *prt, *ch;

		static Node* create(const T& x) {
			static Node pool[N];
			static Node* p = pool;
			p->k = x;
			return p++;
		}
	};

	int n;
	Compare comp;
	Node *min;

	FibHeap(const Compare& comp = Compare()) : n(), comp(comp), min() {}

	int size() const { return n; }
	T top() const { return min->k; }

	Node* insert(const T& x) {
		++n;
		Node* p = Node::create(x);
		if (!min) {
			min = p;
			p->nxt = p->prv = p;
		} else {
			p->prv = min;
			p->nxt = min->nxt;
			p->prv->nxt = p->nxt->prv = p;
			if (comp(p->k, min->k))
				min = p;
		}
		return p;
	}

	void merge(FibHeap& h) {
		n += h.n;
		if (!min) {
			min = h.min;
			h.min = NULL;
			return;
		}
		if (!h.min)
			return;
		h.min->prv = min;
		h.min->nxt = min->nxt;
		h.min->prv->nxt = h.min->nxt->prv = h.min;
		if (comp(h.min->k, min->k))
			min = h.min;
		h.min = NULL;
	}

	/* TODO consolidate, decrease-key */
	void link(Node* y, Node* x) {

	}

	void consolidate() {

	}

	T pop() {
		--n;
		Node* z = min;
		if (z->ch) {
			Node* p = z->ch->nxt;
			while (p != z->ch) {
				p->prv->nxt = p->nxt;
				p->nxt->prv = p->prv;
				p->prt = NULL;
				p->nxt = min->nxt;
				p->prv = min->prv;
				p->nxt->prv = p->prv->nxt = p;
				p = z->ch->nxt;
			}
			p->prt = NULL;
			p->nxt = min->nxt;
			p->prv = min->prv;
			p->nxt->prv = p->prv->nxt = p;
			z->ch = NULL;
		}
		z->prv->nxt = z->nxt;
		z->nxt->prv = z->prv;
		if (z->nxt == z)
			min = NULL;
		else {
			min = z->nxt;
			consolidate();
		}
		return z->k;
	}
};