|
klao@37
|
1 |
#ifndef BIN_HEAP_HH
|
|
klao@37
|
2 |
#define BIN_HEAP_HH
|
|
klao@37
|
3 |
|
|
klao@37
|
4 |
#include <vector>
|
|
klao@37
|
5 |
#include <utility>
|
|
klao@37
|
6 |
#include <functional>
|
|
klao@37
|
7 |
|
|
klao@37
|
8 |
namespace marci {
|
|
klao@37
|
9 |
|
|
klao@37
|
10 |
template <typename Key, typename Val, typename KeyIntMap,
|
|
klao@37
|
11 |
typename Compare = std::less<Val> >
|
|
klao@37
|
12 |
class BinHeap {
|
|
klao@37
|
13 |
|
|
klao@37
|
14 |
public:
|
|
klao@37
|
15 |
typedef Key KeyType;
|
|
klao@37
|
16 |
// FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
|
|
klao@37
|
17 |
typedef Val ValueType;
|
|
klao@37
|
18 |
typedef std::pair<KeyType,ValueType> PairType;
|
|
klao@37
|
19 |
typedef KeyIntMap KeyIntMapType;
|
|
klao@37
|
20 |
typedef Compare ValueCompare;
|
|
klao@37
|
21 |
|
|
klao@37
|
22 |
/**
|
|
klao@37
|
23 |
* Each Key element have a state associated to it. It may be "in heap",
|
|
klao@37
|
24 |
* "pre heap" or "post heap". The later two are indifferent from the
|
|
klao@37
|
25 |
* heap's point of view, but may be useful to the user.
|
|
klao@37
|
26 |
*
|
|
klao@37
|
27 |
* The KeyIntMap _should_ be initialized in such way, that it maps
|
|
klao@37
|
28 |
* PRE_HEAP (-1) to any element to be put in the heap...
|
|
klao@37
|
29 |
*/
|
|
klao@37
|
30 |
|
|
klao@37
|
31 |
enum state {
|
|
klao@37
|
32 |
IN_HEAP = 0,
|
|
klao@37
|
33 |
PRE_HEAP = -1,
|
|
klao@37
|
34 |
POST_HEAP = -2
|
|
klao@37
|
35 |
};
|
|
klao@37
|
36 |
|
|
klao@37
|
37 |
private:
|
|
klao@37
|
38 |
std::vector<PairType> data;
|
|
klao@37
|
39 |
Compare comp;
|
|
klao@37
|
40 |
// FIXME: jo ez igy???
|
|
klao@37
|
41 |
KeyIntMap &kim;
|
|
klao@37
|
42 |
|
|
klao@37
|
43 |
public:
|
|
klao@37
|
44 |
BinHeap(KeyIntMap &_kim) : kim(_kim) {}
|
|
klao@37
|
45 |
BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
|
|
klao@37
|
46 |
|
|
klao@37
|
47 |
|
|
klao@37
|
48 |
int size() const { return data.size(); }
|
|
klao@37
|
49 |
bool empty() const { return size() == 0; }
|
|
klao@37
|
50 |
|
|
klao@37
|
51 |
private:
|
|
klao@37
|
52 |
static int parent(int i) { return (i-1)/2; }
|
|
klao@37
|
53 |
static int second_child(int i) { return 2*i+2; }
|
|
klao@37
|
54 |
bool less(const PairType &p1, const PairType &p2) {
|
|
klao@37
|
55 |
return comp(p1.second, p2.second);
|
|
klao@37
|
56 |
}
|
|
klao@37
|
57 |
|
|
klao@37
|
58 |
int bubble_up(int hole, PairType p);
|
|
klao@37
|
59 |
int bubble_down(int hole, PairType p, int length);
|
|
klao@37
|
60 |
|
|
klao@37
|
61 |
void move(const PairType &p, int i) {
|
|
klao@37
|
62 |
data[i] = p;
|
|
klao@37
|
63 |
kim.put(p.first, i);
|
|
klao@37
|
64 |
}
|
|
klao@37
|
65 |
|
|
klao@37
|
66 |
public:
|
|
klao@37
|
67 |
void push(const PairType &p) {
|
|
klao@37
|
68 |
int n = data.size();
|
|
klao@37
|
69 |
data.resize(n+1);
|
|
klao@37
|
70 |
bubble_up(n, p);
|
|
klao@37
|
71 |
}
|
|
klao@37
|
72 |
void push(const Key &k, const Val &v) { push(PairType(k,v)); }
|
|
klao@37
|
73 |
|
|
klao@37
|
74 |
Key top() const {
|
|
klao@37
|
75 |
// FIXME: test size>0 ?
|
|
klao@37
|
76 |
return data[0].first;
|
|
klao@37
|
77 |
}
|
|
klao@37
|
78 |
Val topValue() const {
|
|
klao@37
|
79 |
// FIXME: test size>0 ?
|
|
klao@37
|
80 |
return data[0].second;
|
|
klao@37
|
81 |
}
|
|
klao@37
|
82 |
|
|
klao@37
|
83 |
void pop() {
|
|
klao@37
|
84 |
int n = data.size()-1;
|
|
klao@37
|
85 |
if ( n>0 ) {
|
|
klao@37
|
86 |
bubble_down(0, data[n], n);
|
|
klao@37
|
87 |
}
|
|
klao@37
|
88 |
if ( n>=0 ) {
|
|
klao@37
|
89 |
data.pop_back();
|
|
klao@37
|
90 |
}
|
|
klao@37
|
91 |
}
|
|
klao@37
|
92 |
|
|
klao@37
|
93 |
const Val get(const Key &k) const {
|
|
klao@37
|
94 |
int idx = kim.get(k);
|
|
klao@37
|
95 |
return data[idx].second;
|
|
klao@37
|
96 |
}
|
|
klao@37
|
97 |
void put(const Key &k, const Val &v) {
|
|
klao@37
|
98 |
int idx = kim.get(k);
|
|
klao@37
|
99 |
if( idx < 0 ) {
|
|
klao@37
|
100 |
push(k,v);
|
|
klao@37
|
101 |
}
|
|
klao@37
|
102 |
else if( comp(v, data[idx].second) ) {
|
|
klao@37
|
103 |
bubble_up(idx, PairType(k,v));
|
|
klao@37
|
104 |
}
|
|
klao@37
|
105 |
else {
|
|
klao@37
|
106 |
bubble_down(idx, PairType(k,v), data.size());
|
|
klao@37
|
107 |
}
|
|
klao@37
|
108 |
}
|
|
klao@37
|
109 |
|
|
klao@37
|
110 |
void decrease(const Key &k, const Val &v) {
|
|
klao@37
|
111 |
int idx = kim.get(k);
|
|
klao@37
|
112 |
bubble_up(idx, PairType(k,v));
|
|
klao@37
|
113 |
}
|
|
klao@37
|
114 |
void increase(const Key &k, const Val &v) {
|
|
klao@37
|
115 |
int idx = kim.get(k);
|
|
klao@37
|
116 |
bubble_down(idx, PairType(k,v), data.size());
|
|
klao@37
|
117 |
}
|
|
klao@37
|
118 |
|
|
klao@37
|
119 |
}; // class BinHeap
|
|
klao@37
|
120 |
|
|
klao@37
|
121 |
|
|
klao@37
|
122 |
template <typename K, typename V, typename M, typename C>
|
|
klao@37
|
123 |
int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
|
|
klao@37
|
124 |
int par = parent(hole);
|
|
klao@37
|
125 |
while( hole>0 && less(p,data[par]) ) {
|
|
klao@37
|
126 |
move(data[par],hole);
|
|
klao@37
|
127 |
hole = par;
|
|
klao@37
|
128 |
par = parent(hole);
|
|
klao@37
|
129 |
}
|
|
klao@37
|
130 |
move(p, hole);
|
|
klao@37
|
131 |
return hole;
|
|
klao@37
|
132 |
}
|
|
klao@37
|
133 |
|
|
klao@37
|
134 |
template <typename K, typename V, typename M, typename C>
|
|
klao@37
|
135 |
int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
|
|
klao@37
|
136 |
int child = second_child(hole);
|
|
klao@37
|
137 |
while(child < length) {
|
|
klao@37
|
138 |
if( less(data[child-1], data[child]) ) {
|
|
klao@37
|
139 |
--child;
|
|
klao@37
|
140 |
}
|
|
klao@37
|
141 |
if( !less(data[child], p) )
|
|
klao@37
|
142 |
goto ok;
|
|
klao@37
|
143 |
move(data[child], hole);
|
|
klao@37
|
144 |
hole = child;
|
|
klao@37
|
145 |
child = second_child(hole);
|
|
klao@37
|
146 |
}
|
|
klao@37
|
147 |
child--;
|
|
klao@37
|
148 |
if( child<length && less(data[child], p) ) {
|
|
klao@37
|
149 |
move(data[child], hole);
|
|
klao@37
|
150 |
hole=child;
|
|
klao@37
|
151 |
}
|
|
klao@37
|
152 |
ok:
|
|
klao@37
|
153 |
move(p, hole);
|
|
klao@37
|
154 |
return hole;
|
|
klao@37
|
155 |
}
|
|
klao@37
|
156 |
|
|
klao@37
|
157 |
} // namespace marci
|
|
klao@37
|
158 |
|
|
klao@37
|
159 |
#endif // BIN_HEAP_HH
|