alpar@255: // -*- C++ -*- alpar@255: jacint@373: #ifndef HUGO_FIB_HEAP_H jacint@373: #define HUGO_FIB_HEAP_H alpar@255: alpar@430: ///ingroup auxdat alpar@255: ///\file alpar@255: ///\brief Fibonacci Heap implementation. alpar@255: alpar@255: #include alpar@255: #include alpar@255: #include alpar@255: alpar@255: namespace hugo { alpar@255: alpar@430: /// \addtogroup auxdat alpar@430: /// @{ alpar@430: jacint@373: /// An implementation of the Fibonacci Heap. jacint@373: jacint@373: /** jacint@387: This class implements the \e Fibonacci \e heap data structure. A \e heap jacint@387: is a data structure for storing items with specified values called \e jacint@387: priorities, such that finding the item with minimum priority with respect jacint@387: to \e Compare is efficient. In a heap one can change the priority of an jacint@387: item, add or erase an item, etc. jacint@373: jacint@387: The methods \ref increase and \ref erase are not efficient in a Fibonacci jacint@387: heap. In case of many calls to these operations, it is better to use a jacint@387: \e binary \e heap. jacint@373: jacint@387: \param Item The type of the items to be stored. jacint@387: \param Prio The type of the priority of the items. jacint@387: \param ItemIntMap A read and writable Item int map, for the usage of jacint@373: the heap. jacint@387: \param Compare A class for the comparison of the priorities. The jacint@373: default is \c std::less. jacint@373: jacint@373: */ jacint@373: jacint@373: #ifdef DOXYGEN jacint@373: template jacint@373: #else jacint@373: template > jacint@373: #endif alpar@255: class FibHeap { jacint@387: public: alpar@255: typedef Prio PrioType; alpar@255: jacint@373: private: alpar@255: class store; alpar@255: alpar@255: std::vector container; alpar@255: int minimum; alpar@255: ItemIntMap &iimap; alpar@255: Compare comp; alpar@255: int num_items; jacint@373: alpar@255: public: alpar@255: enum state_enum { alpar@255: IN_HEAP = 0, alpar@255: PRE_HEAP = -1, alpar@255: POST_HEAP = -2 alpar@255: }; alpar@255: jacint@373: FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} jacint@373: FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), alpar@255: iimap(_iimap), comp(_comp), num_items() {} alpar@255: jacint@373: ///The number of items stored in the heap. jacint@373: jacint@373: /** jacint@387: Returns the number of items stored in the heap. jacint@373: */ jacint@373: int size() const { return num_items; } jacint@373: jacint@373: ///Checks if the heap stores no items. alpar@255: jacint@373: /** jacint@387: Returns \c true iff the heap stores no items. jacint@373: */ jacint@373: bool empty() const { return num_items==0; } jacint@373: jacint@387: ///\c item gets to the heap with priority \c value independently if \c item was already there. jacint@373: jacint@373: /** jacint@387: This method calls \ref push(\c item, \c value) if \c item is not jacint@387: stored in the heap and it calls \ref decrease(\c item, \c value) or jacint@387: \ref increase(\c item, \c value) otherwise. jacint@373: */ jacint@387: void set (Item const item, PrioType const value); jacint@373: jacint@373: ///Adds \c item to the heap with priority \c value. jacint@373: jacint@373: /** jacint@373: Adds \c item to the heap with priority \c value. jacint@373: \pre \c item must not be stored in the heap. jacint@373: */ jacint@387: void push (Item const item, PrioType const value); jacint@373: jacint@373: jacint@373: ///Returns the item having the minimum priority w.r.t. Compare. jacint@373: jacint@373: /** jacint@373: This method returns the item having the minimum priority w.r.t. Compare. jacint@373: \pre The heap must be nonempty. jacint@373: */ jacint@373: Item top() const { return container[minimum].name; } jacint@373: jacint@373: jacint@373: ///Returns the minimum priority w.r.t. Compare. jacint@373: jacint@373: /** jacint@373: It returns the minimum priority w.r.t. Compare. jacint@373: \pre The heap must be nonempty. jacint@373: */ jacint@373: PrioType prio() const { return container[minimum].prio; } jacint@373: jacint@373: jacint@373: ///Returns the priority of \c item. jacint@373: jacint@373: /** jacint@373: It returns the priority of \c item. jacint@373: \pre \c item must be in the heap. jacint@373: */ jacint@387: PrioType& operator[](const Item& item) { jacint@387: return container[iimap[item]].prio; jacint@387: } jacint@373: jacint@373: ///Returns the priority of \c item. jacint@373: jacint@373: /** jacint@373: It returns the priority of \c item. jacint@373: \pre \c item must be in the heap. jacint@373: */ jacint@387: const PrioType& operator[](const Item& item) const { jacint@387: return container[iimap[item]].prio; alpar@255: } alpar@255: alpar@255: jacint@373: ///Deletes the item with minimum priority w.r.t. Compare. alpar@255: jacint@373: /** jacint@373: This method deletes the item with minimum priority w.r.t. jacint@373: Compare from the heap. jacint@373: \pre The heap must be non-empty. jacint@373: */ jacint@373: void pop(); jacint@373: jacint@373: ///Deletes \c item from the heap. jacint@373: jacint@373: /** jacint@373: This method deletes \c item from the heap, if \c item was already jacint@373: stored in the heap. It is quite inefficient in Fibonacci heaps. jacint@373: */ jacint@387: void erase (const Item& item); jacint@373: jacint@373: ///Decreases the priority of \c item to \c value. jacint@373: jacint@373: /** jacint@373: This method decreases the priority of \c item to \c value. jacint@373: \pre \c item must be stored in the heap with priority at least \c jacint@373: value w.r.t. Compare. jacint@373: */ jacint@387: void decrease (Item item, PrioType const value); jacint@373: jacint@373: jacint@373: ///Increases the priority of \c item to \c value. jacint@373: jacint@373: /** jacint@373: This method sets the priority of \c item to \c value. Though jacint@373: there is no precondition on the priority of \c item, this jacint@387: method should be used only if there is a need to really \e increase jacint@373: (w.r.t. Compare) the priority of \c item, because this jacint@373: method is inefficient. jacint@373: */ jacint@387: void increase (Item item, PrioType const value) { jacint@387: erase(item); jacint@387: push(item, value); jacint@373: } jacint@373: jacint@373: jacint@387: ///Tells if \c item is in, was already in, or has never been in the heap. jacint@373: jacint@373: /** jacint@373: This method returns PRE_HEAP if \c item has never been in the jacint@373: heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP jacint@373: otherwise. In the latter case it is possible that \c item will jacint@373: get back to the heap again. jacint@373: */ jacint@387: state_enum state(const Item &item) const { jacint@387: int i=iimap[item]; jacint@387: if( i>=0 ) { jacint@387: if ( container[i].in ) i=0; jacint@387: else i=-2; jacint@387: } jacint@387: return state_enum(i); jacint@387: } jacint@387: jacint@387: private: jacint@387: jacint@387: void balance(); jacint@387: void makeroot(int c); jacint@387: void cut(int a, int b); jacint@387: void cascade(int a); jacint@387: void fuse(int a, int b); jacint@387: void unlace(int a); jacint@373: jacint@373: jacint@387: class store { jacint@387: friend class FibHeap; jacint@387: jacint@387: Item name; jacint@387: int parent; jacint@387: int left_neighbor; jacint@387: int right_neighbor; jacint@387: int child; jacint@387: int degree; jacint@387: bool marked; jacint@387: bool in; jacint@387: PrioType prio; jacint@387: jacint@387: store() : parent(-1), child(-1), degree(), marked(false), in(true) {} jacint@387: }; jacint@387: }; jacint@387: jacint@387: jacint@373: jacint@373: // ********************************************************************** jacint@373: // IMPLEMENTATIONS jacint@373: // ********************************************************************** jacint@373: jacint@387: template jacint@387: void FibHeap::set jacint@387: (Item const item, PrioType const value) jacint@387: { jacint@387: int i=iimap[item]; jacint@387: if ( i >= 0 && container[i].in ) { jacint@387: if ( comp(value, container[i].prio) ) decrease(item, value); jacint@387: if ( comp(container[i].prio, value) ) increase(item, value); jacint@387: } else push(item, value); jacint@387: } alpar@255: jacint@387: template jacint@387: void FibHeap::push jacint@387: (Item const item, PrioType const value) { jacint@387: int i=iimap[item]; alpar@255: if ( i < 0 ) { alpar@255: int s=container.size(); jacint@387: iimap.set( item, s ); alpar@255: store st; jacint@387: st.name=item; alpar@255: container.push_back(st); alpar@255: i=s; alpar@255: } else { alpar@255: container[i].parent=container[i].child=-1; alpar@255: container[i].degree=0; alpar@255: container[i].in=true; alpar@255: container[i].marked=false; alpar@255: } alpar@255: alpar@255: if ( num_items ) { alpar@255: container[container[minimum].right_neighbor].left_neighbor=i; alpar@255: container[i].right_neighbor=container[minimum].right_neighbor; alpar@255: container[minimum].right_neighbor=i; alpar@255: container[i].left_neighbor=minimum; alpar@255: if ( comp( value, container[minimum].prio) ) minimum=i; alpar@255: } else { alpar@255: container[i].right_neighbor=container[i].left_neighbor=i; alpar@255: minimum=i; alpar@255: } alpar@255: container[i].prio=value; alpar@255: ++num_items; alpar@255: } alpar@255: jacint@387: template jacint@387: void FibHeap::pop() { alpar@255: /*The first case is that there are only one root.*/ alpar@255: if ( container[minimum].left_neighbor==minimum ) { alpar@255: container[minimum].in=false; alpar@255: if ( container[minimum].degree!=0 ) { alpar@255: makeroot(container[minimum].child); alpar@255: minimum=container[minimum].child; alpar@255: balance(); alpar@255: } alpar@255: } else { alpar@255: int right=container[minimum].right_neighbor; alpar@255: unlace(minimum); alpar@255: container[minimum].in=false; alpar@255: if ( container[minimum].degree > 0 ) { alpar@255: int left=container[minimum].left_neighbor; alpar@255: int child=container[minimum].child; alpar@255: int last_child=container[child].left_neighbor; alpar@255: alpar@255: makeroot(child); alpar@255: alpar@255: container[left].right_neighbor=child; alpar@255: container[child].left_neighbor=left; alpar@255: container[right].left_neighbor=last_child; alpar@255: container[last_child].right_neighbor=right; alpar@255: } alpar@255: minimum=right; alpar@255: balance(); alpar@255: } // the case where there are more roots alpar@255: --num_items; alpar@255: } alpar@255: jacint@387: jacint@387: template jacint@387: void FibHeap::erase jacint@387: (const Item& item) { jacint@387: int i=iimap[item]; alpar@255: alpar@255: if ( i >= 0 && container[i].in ) { alpar@255: if ( container[i].parent!=-1 ) { alpar@255: int p=container[i].parent; alpar@255: cut(i,p); alpar@255: cascade(p); alpar@255: } alpar@255: minimum=i; //As if its prio would be -infinity alpar@255: pop(); alpar@255: } jacint@387: } alpar@255: jacint@387: template jacint@387: void FibHeap::decrease jacint@387: (Item item, PrioType const value) { jacint@387: int i=iimap[item]; alpar@255: container[i].prio=value; alpar@255: int p=container[i].parent; alpar@255: alpar@255: if ( p!=-1 && comp(value, container[p].prio) ) { alpar@255: cut(i,p); alpar@255: cascade(p); alpar@255: } alpar@255: if ( comp(value, container[minimum].prio) ) minimum=i; jacint@387: } jacint@387: alpar@255: jacint@387: template jacint@387: void FibHeap::balance() { alpar@255: alpar@255: int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; alpar@255: alpar@255: std::vector A(maxdeg,-1); alpar@255: alpar@255: /* alpar@255: *Recall that now minimum does not point to the minimum prio element. alpar@255: *We set minimum to this during balance(). alpar@255: */ alpar@255: int anchor=container[minimum].left_neighbor; alpar@255: int next=minimum; alpar@255: bool end=false; alpar@255: alpar@255: do { alpar@255: int active=next; alpar@255: if ( anchor==active ) end=true; alpar@255: int d=container[active].degree; alpar@255: next=container[active].right_neighbor; alpar@255: alpar@255: while (A[d]!=-1) { alpar@255: if( comp(container[active].prio, container[A[d]].prio) ) { alpar@255: fuse(active,A[d]); alpar@255: } else { alpar@255: fuse(A[d],active); alpar@255: active=A[d]; alpar@255: } alpar@255: A[d]=-1; alpar@255: ++d; alpar@255: } alpar@255: A[d]=active; alpar@255: } while ( !end ); alpar@255: alpar@255: alpar@255: while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; alpar@255: int s=minimum; alpar@255: int m=minimum; alpar@255: do { alpar@255: if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; alpar@255: s=container[s].right_neighbor; alpar@255: } while ( s != m ); alpar@255: } alpar@255: jacint@387: template jacint@387: void FibHeap::makeroot jacint@387: (int c) { alpar@255: int s=c; alpar@255: do { alpar@255: container[s].parent=-1; alpar@255: s=container[s].right_neighbor; alpar@255: } while ( s != c ); alpar@255: } jacint@387: jacint@387: jacint@387: template jacint@387: void FibHeap::cut jacint@387: (int a, int b) { jacint@387: /* jacint@387: *Replacing a from the children of b. jacint@387: */ jacint@387: --container[b].degree; alpar@255: jacint@387: if ( container[b].degree !=0 ) { jacint@387: int child=container[b].child; jacint@387: if ( child==a ) jacint@387: container[b].child=container[child].right_neighbor; jacint@387: unlace(a); jacint@387: } jacint@387: jacint@387: jacint@387: /*Lacing a to the roots.*/ jacint@387: int right=container[minimum].right_neighbor; jacint@387: container[minimum].right_neighbor=a; jacint@387: container[a].left_neighbor=minimum; jacint@387: container[a].right_neighbor=right; jacint@387: container[right].left_neighbor=a; jacint@387: jacint@387: container[a].parent=-1; jacint@387: container[a].marked=false; jacint@387: } jacint@387: alpar@255: jacint@387: template jacint@387: void FibHeap::cascade jacint@387: (int a) alpar@255: { alpar@255: if ( container[a].parent!=-1 ) { alpar@255: int p=container[a].parent; alpar@255: alpar@255: if ( container[a].marked==false ) container[a].marked=true; alpar@255: else { alpar@255: cut(a,p); alpar@255: cascade(p); alpar@255: } alpar@255: } alpar@255: } alpar@255: alpar@255: jacint@387: template jacint@387: void FibHeap::fuse jacint@387: (int a, int b) { alpar@255: unlace(b); alpar@255: alpar@255: /*Lacing b under a.*/ alpar@255: container[b].parent=a; alpar@255: alpar@255: if (container[a].degree==0) { alpar@255: container[b].left_neighbor=b; alpar@255: container[b].right_neighbor=b; alpar@255: container[a].child=b; alpar@255: } else { alpar@255: int child=container[a].child; alpar@255: int last_child=container[child].left_neighbor; alpar@255: container[child].left_neighbor=b; alpar@255: container[b].right_neighbor=child; alpar@255: container[last_child].right_neighbor=b; alpar@255: container[b].left_neighbor=last_child; alpar@255: } alpar@255: alpar@255: ++container[a].degree; alpar@255: alpar@255: container[b].marked=false; alpar@255: } alpar@255: jacint@387: jacint@387: /* jacint@387: *It is invoked only if a has siblings. jacint@387: */ jacint@387: template jacint@387: void FibHeap::unlace jacint@387: (int a) { alpar@255: int leftn=container[a].left_neighbor; alpar@255: int rightn=container[a].right_neighbor; alpar@255: container[leftn].right_neighbor=rightn; alpar@255: container[rightn].left_neighbor=leftn; jacint@387: } alpar@255: alpar@430: ///@} alpar@430: alpar@255: } //namespace hugo alpar@477: alpar@477: #endif //HUGO_FIB_HEAP_H alpar@477: