jacint@167: // -*- C++ -*-
jacint@167: /*
jacint@167: *template <typename Item,
jacint@167: * typename Prio,
jacint@167: * typename ItemIntMap,
jacint@167: * typename Compare = std::less<Prio> >
jacint@167: *
jacint@167: *constructors:
jacint@167: *
jacint@167: *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
jacint@167: *
jacint@167: *Member functions:
jacint@167: *
jacint@167: *int size() : returns the number of elements in the heap
jacint@167: *
jacint@167: *bool empty() : true iff size()=0
jacint@167: *
jacint@167: *void set(Item, Prio) : calls push(Item, Prio) if Item is not
jacint@167: * in the heap, and calls decrease/increase(Item, Prio) otherwise
jacint@167: *
jacint@167: *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
jacint@167: * mustn't be in the heap.
jacint@167: *
jacint@173: *Item top() : returns the Item with least Prio.
jacint@173: * Must be called only if heap is nonempty.
jacint@167: *
jacint@167: *Prio prio() : returns the least Prio
jacint@173: * Must be called only if heap is nonempty.
jacint@173: *
jacint@167: *Prio get(Item) : returns Prio of Item
jacint@173: * Must be called only if Item is in heap.
jacint@167: *
jacint@167: *void pop() : deletes the Item with least Prio
jacint@167: *
jacint@167: *void erase(Item) : deletes Item from the heap if it was already there
jacint@167: *
jacint@167: *void decrease(Item, P) : decreases prio of Item to P.
jacint@167: * Item must be in the heap with prio at least P.
jacint@167: *
jacint@167: *void increase(Item, P) : sets prio of Item to P.
jacint@167: *
jacint@167: *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
jacint@167: * heap until now, IN_HEAP if it is in the heap at the moment, and
jacint@167: * POST_HEAP otherwise. In the latter case it is possible that Item
jacint@167: * will get back to the heap again.
jacint@167: *
jacint@167: *In Fibonacci heaps, increase and erase are not efficient, in case of
jacint@167: *many calls to these operations, it is better to use bin_heap.
jacint@167: */
jacint@167:
jacint@167: #ifndef FIB_HEAP_H
jacint@167: #define FIB_HEAP_H
jacint@167:
jacint@167: #include <vector>
jacint@167: #include <functional>
jacint@167: #include <math.h>
jacint@167:
jacint@167: namespace hugo {
jacint@167:
jacint@167: template <typename Item, typename Prio, typename ItemIntMap,
jacint@167: typename Compare = std::less<Prio> >
jacint@167:
jacint@167: class FibHeap {
jacint@167:
jacint@167: typedef Prio PrioType;
jacint@167:
jacint@167: class store;
jacint@167:
jacint@167: std::vector<store> container;
jacint@167: int minimum;
jacint@167: ItemIntMap &iimap;
jacint@167: Compare comp;
jacint@173: int num_items;
jacint@167:
jacint@167: enum state_enum {
jacint@167: IN_HEAP = 0,
jacint@167: PRE_HEAP = -1,
jacint@167: POST_HEAP = -2
jacint@167: };
jacint@167:
jacint@167: public :
jacint@167:
jacint@173: FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
jacint@167: FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
jacint@173: iimap(_iimap), comp(_comp), num_items() {}
jacint@167:
jacint@167:
jacint@167: int size() const {
jacint@173: return num_items;
jacint@167: }
jacint@167:
jacint@167:
jacint@173: bool empty() const { return num_items==0; }
jacint@167:
jacint@167:
jacint@167: void set (Item const it, PrioType const value) {
alpar@217: int i=iimap[it];
jacint@167: if ( i >= 0 && container[i].in ) {
jacint@173: if ( comp(value, container[i].prio) ) decrease(it, value);
jacint@167: if ( comp(container[i].prio, value) ) increase(it, value);
jacint@167: } else push(it, value);
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void push (Item const it, PrioType const value) {
alpar@217: int i=iimap[it];
jacint@167: if ( i < 0 ) {
jacint@167: int s=container.size();
jacint@167: iimap.set( it, s );
jacint@167: store st;
jacint@167: st.name=it;
jacint@167: container.push_back(st);
jacint@167: i=s;
jacint@167: } else {
jacint@167: container[i].parent=container[i].child=-1;
jacint@167: container[i].degree=0;
jacint@167: container[i].in=true;
jacint@167: container[i].marked=false;
jacint@167: }
jacint@167:
jacint@173: if ( num_items ) {
jacint@167: container[container[minimum].right_neighbor].left_neighbor=i;
jacint@167: container[i].right_neighbor=container[minimum].right_neighbor;
jacint@167: container[minimum].right_neighbor=i;
jacint@167: container[i].left_neighbor=minimum;
jacint@173: if ( comp( value, container[minimum].prio) ) minimum=i;
jacint@167: } else {
jacint@167: container[i].right_neighbor=container[i].left_neighbor=i;
jacint@167: minimum=i;
jacint@167: }
jacint@167: container[i].prio=value;
jacint@173: ++num_items;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: Item top() const {
jacint@173: return container[minimum].name;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: PrioType prio() const {
jacint@173: return container[minimum].prio;
jacint@167: }
jacint@167:
jacint@167:
alpar@217: PrioType& operator[](const Item& it) {
alpar@217: return container[iimap[it]].prio;
jacint@211: }
jacint@220:
jacint@211:
jacint@211: const PrioType& operator[](const Item& it) const {
alpar@217: return container[iimap[it]].prio;
jacint@211: }
jacint@211:
jacint@211:
jacint@220: const PrioType get(const Item& it) const {
jacint@220: return container[iimap[it]].prio;
jacint@220: }
jacint@220:
jacint@167: void pop() {
jacint@167: /*The first case is that there are only one root.*/
jacint@167: if ( container[minimum].left_neighbor==minimum ) {
jacint@167: container[minimum].in=false;
jacint@173: if ( container[minimum].degree!=0 ) {
jacint@167: makeroot(container[minimum].child);
jacint@167: minimum=container[minimum].child;
jacint@167: balance();
jacint@173: }
jacint@167: } else {
jacint@167: int right=container[minimum].right_neighbor;
jacint@167: unlace(minimum);
jacint@167: container[minimum].in=false;
jacint@167: if ( container[minimum].degree > 0 ) {
jacint@167: int left=container[minimum].left_neighbor;
jacint@167: int child=container[minimum].child;
jacint@167: int last_child=container[child].left_neighbor;
jacint@167:
jacint@167: makeroot(child);
jacint@167:
jacint@167: container[left].right_neighbor=child;
jacint@167: container[child].left_neighbor=left;
jacint@167: container[right].left_neighbor=last_child;
jacint@167: container[last_child].right_neighbor=right;
jacint@167: }
jacint@167: minimum=right;
jacint@167: balance();
jacint@167: } // the case where there are more roots
jacint@173: --num_items;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void erase (const Item& it) {
alpar@217: int i=iimap[it];
jacint@167:
jacint@173: if ( i >= 0 && container[i].in ) {
jacint@173: if ( container[i].parent!=-1 ) {
jacint@173: int p=container[i].parent;
jacint@173: cut(i,p);
jacint@173: cascade(p);
jacint@173: }
jacint@173: minimum=i; //As if its prio would be -infinity
jacint@173: pop();
jacint@173: }
jacint@173: }
jacint@167:
jacint@167:
jacint@167: void decrease (Item it, PrioType const value) {
alpar@217: int i=iimap[it];
jacint@167: container[i].prio=value;
jacint@167: int p=container[i].parent;
jacint@167:
jacint@167: if ( p!=-1 && comp(value, container[p].prio) ) {
jacint@167: cut(i,p);
jacint@167: cascade(p);
jacint@173: }
jacint@173: if ( comp(value, container[minimum].prio) ) minimum=i;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void increase (Item it, PrioType const value) {
jacint@167: erase(it);
jacint@167: push(it, value);
jacint@167: }
jacint@167:
jacint@167:
jacint@167: state_enum state(const Item &it) const {
alpar@217: int i=iimap[it];
jacint@167: if( i>=0 ) {
jacint@241: if ( container[i].in ) i=IN_HEAP;
jacint@241: else i=POST_HEAP;
jacint@167: }
jacint@167: return state_enum(i);
jacint@167: }
jacint@167:
jacint@167:
jacint@167: private:
jacint@167:
jacint@167: void balance() {
jacint@167:
jacint@167: int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
jacint@167:
jacint@167: std::vector<int> A(maxdeg,-1);
jacint@167:
jacint@167: /*
jacint@167: *Recall that now minimum does not point to the minimum prio element.
jacint@167: *We set minimum to this during balance().
jacint@167: */
jacint@167: int anchor=container[minimum].left_neighbor;
jacint@167: int next=minimum;
jacint@167: bool end=false;
jacint@167:
jacint@167: do {
jacint@167: int active=next;
jacint@167: if ( anchor==active ) end=true;
jacint@167: int d=container[active].degree;
jacint@167: next=container[active].right_neighbor;
jacint@167:
jacint@167: while (A[d]!=-1) {
jacint@167: if( comp(container[active].prio, container[A[d]].prio) ) {
jacint@167: fuse(active,A[d]);
jacint@167: } else {
jacint@167: fuse(A[d],active);
jacint@167: active=A[d];
jacint@167: }
jacint@167: A[d]=-1;
jacint@167: ++d;
jacint@167: }
jacint@167: A[d]=active;
jacint@167: } while ( !end );
jacint@167:
jacint@167:
jacint@167: while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
jacint@167: int s=minimum;
jacint@167: int m=minimum;
jacint@167: do {
jacint@167: if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
jacint@167: s=container[s].right_neighbor;
jacint@167: } while ( s != m );
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void makeroot (int c) {
jacint@167: int s=c;
jacint@167: do {
jacint@167: container[s].parent=-1;
jacint@167: s=container[s].right_neighbor;
jacint@167: } while ( s != c );
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void cut (int a, int b) {
jacint@167: /*
jacint@167: *Replacing a from the children of b.
jacint@167: */
jacint@167: --container[b].degree;
jacint@167:
jacint@167: if ( container[b].degree !=0 ) {
jacint@167: int child=container[b].child;
jacint@167: if ( child==a )
jacint@167: container[b].child=container[child].right_neighbor;
jacint@167: unlace(a);
jacint@167: }
jacint@167:
jacint@167:
jacint@173: /*Lacing a to the roots.*/
jacint@167: int right=container[minimum].right_neighbor;
jacint@167: container[minimum].right_neighbor=a;
jacint@167: container[a].left_neighbor=minimum;
jacint@167: container[a].right_neighbor=right;
jacint@167: container[right].left_neighbor=a;
jacint@167:
jacint@167: container[a].parent=-1;
jacint@167: container[a].marked=false;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void cascade (int a)
jacint@167: {
jacint@167: if ( container[a].parent!=-1 ) {
jacint@167: int p=container[a].parent;
jacint@167:
jacint@167: if ( container[a].marked==false ) container[a].marked=true;
jacint@167: else {
jacint@167: cut(a,p);
jacint@167: cascade(p);
jacint@167: }
jacint@167: }
jacint@167: }
jacint@167:
jacint@167:
jacint@167: void fuse (int a, int b) {
jacint@167: unlace(b);
jacint@167:
jacint@167: /*Lacing b under a.*/
jacint@167: container[b].parent=a;
jacint@167:
jacint@167: if (container[a].degree==0) {
jacint@167: container[b].left_neighbor=b;
jacint@167: container[b].right_neighbor=b;
jacint@167: container[a].child=b;
jacint@167: } else {
jacint@167: int child=container[a].child;
jacint@167: int last_child=container[child].left_neighbor;
jacint@167: container[child].left_neighbor=b;
jacint@167: container[b].right_neighbor=child;
jacint@167: container[last_child].right_neighbor=b;
jacint@167: container[b].left_neighbor=last_child;
jacint@167: }
jacint@167:
jacint@167: ++container[a].degree;
jacint@167:
jacint@167: container[b].marked=false;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: /*
jacint@167: *It is invoked only if a has siblings.
jacint@167: */
jacint@167: void unlace (int a) {
jacint@167: int leftn=container[a].left_neighbor;
jacint@167: int rightn=container[a].right_neighbor;
jacint@167: container[leftn].right_neighbor=rightn;
jacint@167: container[rightn].left_neighbor=leftn;
jacint@167: }
jacint@167:
jacint@167:
jacint@167: class store {
jacint@167: friend class FibHeap;
jacint@167:
jacint@167: Item name;
jacint@167: int parent;
jacint@167: int left_neighbor;
jacint@167: int right_neighbor;
jacint@167: int child;
jacint@167: int degree;
jacint@167: bool marked;
jacint@167: bool in;
jacint@167: PrioType prio;
jacint@167:
jacint@167: store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
jacint@167: };
jacint@167:
jacint@167: };
jacint@167:
jacint@167: } //namespace hugo
jacint@167: #endif