00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_BIN_HEAP_H
00020 #define LEMON_BIN_HEAP_H
00021
00025
00026 #include <vector>
00027 #include <utility>
00028 #include <functional>
00029
00030 namespace lemon {
00031
00033
00035
00051 template <typename Item, typename Prio, typename ItemIntMap,
00052 typename Compare = std::less<Prio> >
00053 class BinHeap {
00054
00055 public:
00056 typedef Item ItemType;
00057
00058 typedef Prio PrioType;
00059 typedef std::pair<ItemType,PrioType> PairType;
00060 typedef ItemIntMap ItemIntMapType;
00061 typedef Compare PrioCompare;
00062
00071 enum state_enum {
00072 IN_HEAP = 0,
00073 PRE_HEAP = -1,
00074 POST_HEAP = -2
00075 };
00076
00077 private:
00078 std::vector<PairType> data;
00079 Compare comp;
00080 ItemIntMap &iim;
00081
00082 public:
00089 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
00090
00099 BinHeap(ItemIntMap &_iim, const Compare &_comp)
00100 : iim(_iim), comp(_comp) {}
00101
00102
00106 int size() const { return data.size(); }
00107
00111 bool empty() const { return data.empty(); }
00112
00116 void clear() {
00117 for (int i = 0; i < (int)data.size(); ++i) {
00118 iim.set(data[i].first, POST_HEAP);
00119 }
00120 data.clear();
00121 }
00122
00123 private:
00124 static int parent(int i) { return (i-1)/2; }
00125 static int second_child(int i) { return 2*i+2; }
00126 bool less(const PairType &p1, const PairType &p2) const {
00127 return comp(p1.second, p2.second);
00128 }
00129
00130 int bubble_up(int hole, PairType p);
00131 int bubble_down(int hole, PairType p, int length);
00132
00133 void move(const PairType &p, int i) {
00134 data[i] = p;
00135 iim.set(p.first, i);
00136 }
00137
00138 void rmidx(int h) {
00139 int n = data.size()-1;
00140 if( h>=0 && h<=n ) {
00141 iim.set(data[h].first, POST_HEAP);
00142 if ( h<n ) {
00143 bubble_down(h, data[n], n);
00144 }
00145 data.pop_back();
00146 }
00147 }
00148
00149 public:
00154 void push(const PairType &p) {
00155 int n = data.size();
00156 data.resize(n+1);
00157 bubble_up(n, p);
00158 }
00159
00165 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
00166
00172 Item top() const {
00173 return data[0].first;
00174 }
00175
00180 Prio prio() const {
00181 return data[0].second;
00182 }
00183
00189 void pop() {
00190 rmidx(0);
00191 }
00192
00198 void erase(const Item &i) {
00199 rmidx(iim[i]);
00200 }
00201
00202
00208 Prio operator[](const Item &i) const {
00209 int idx = iim[i];
00210 return data[idx].second;
00211 }
00212
00220 void set(const Item &i, const Prio &p) {
00221 int idx = iim[i];
00222 if( idx < 0 ) {
00223 push(i,p);
00224 }
00225 else if( comp(p, data[idx].second) ) {
00226 bubble_up(idx, PairType(i,p));
00227 }
00228 else {
00229 bubble_down(idx, PairType(i,p), data.size());
00230 }
00231 }
00232
00234
00240 void decrease(const Item &i, const Prio &p) {
00241 int idx = iim[i];
00242 bubble_up(idx, PairType(i,p));
00243 }
00244
00252 void increase(const Item &i, const Prio &p) {
00253 int idx = iim[i];
00254 bubble_down(idx, PairType(i,p), data.size());
00255 }
00256
00265 state_enum state(const Item &i) const {
00266 int s = iim[i];
00267 if( s>=0 )
00268 s=0;
00269 return state_enum(s);
00270 }
00271
00279 void state(const Item& i, state_enum st) {
00280 switch (st) {
00281 case POST_HEAP:
00282 case PRE_HEAP:
00283 if (state(i) == IN_HEAP) {
00284 erase(i);
00285 }
00286 iim[i] = st;
00287 break;
00288 case IN_HEAP:
00289 break;
00290 }
00291 }
00292
00293 };
00294
00295
00296 template <typename K, typename V, typename M, typename C>
00297 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
00298 int par = parent(hole);
00299 while( hole>0 && less(p,data[par]) ) {
00300 move(data[par],hole);
00301 hole = par;
00302 par = parent(hole);
00303 }
00304 move(p, hole);
00305 return hole;
00306 }
00307
00308 template <typename K, typename V, typename M, typename C>
00309 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
00310 int child = second_child(hole);
00311 while(child < length) {
00312 if( less(data[child-1], data[child]) ) {
00313 --child;
00314 }
00315 if( !less(data[child], p) )
00316 goto ok;
00317 move(data[child], hole);
00318 hole = child;
00319 child = second_child(hole);
00320 }
00321 child--;
00322 if( child<length && less(data[child], p) ) {
00323 move(data[child], hole);
00324 hole=child;
00325 }
00326 ok:
00327 move(p, hole);
00328 return hole;
00329 }
00330
00331
00332 }
00333
00334 #endif // LEMON_BIN_HEAP_H