deba@681: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@681: *
deba@681: * This file is a part of LEMON, a generic C++ optimization library.
deba@681: *
deba@681: * Copyright (C) 2003-2009
deba@681: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@681: * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@681: *
deba@681: * Permission to use, modify and distribute this software is granted
deba@681: * provided that this copyright notice appears in all copies. For
deba@681: * precise terms see the accompanying LICENSE file.
deba@681: *
deba@681: * This software is provided "AS IS" with no warranty of any kind,
deba@681: * express or implied, and with no claim as to its suitability for any
deba@681: * purpose.
deba@681: *
deba@681: */
deba@681:
deba@681: #ifndef LEMON_FIB_HEAP_H
deba@681: #define LEMON_FIB_HEAP_H
deba@681:
deba@681: ///\file
kpeter@710: ///\ingroup heaps
kpeter@709: ///\brief Fibonacci heap implementation.
deba@681:
deba@681: #include <vector>
kpeter@709: #include <utility>
deba@681: #include <functional>
deba@681: #include <lemon/math.h>
deba@681:
deba@681: namespace lemon {
deba@681:
kpeter@710: /// \ingroup heaps
deba@681: ///
kpeter@709: /// \brief Fibonacci heap data structure.
deba@681: ///
kpeter@709: /// This class implements the \e Fibonacci \e heap data structure.
kpeter@709: /// It fully conforms to the \ref concepts::Heap "heap concept".
deba@681: ///
kpeter@709: /// The methods \ref increase() and \ref erase() are not efficient in a
kpeter@709: /// Fibonacci heap. In case of many calls of these operations, it is
kpeter@709: /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
deba@681: ///
kpeter@709: /// \tparam PR Type of the priorities of the items.
kpeter@709: /// \tparam IM A read-writable item map with \c int values, used
kpeter@709: /// internally to handle the cross references.
kpeter@709: /// \tparam CMP A functor class for comparing the priorities.
kpeter@709: /// The default is \c std::less<PR>.
deba@681: #ifdef DOXYGEN
kpeter@709: template <typename PR, typename IM, typename CMP>
deba@681: #else
kpeter@709: template <typename PR, typename IM, typename CMP = std::less<PR> >
deba@681: #endif
deba@681: class FibHeap {
deba@681: public:
kpeter@709:
kpeter@709: /// Type of the item-int map.
deba@683: typedef IM ItemIntMap;
kpeter@709: /// Type of the priorities.
kpeter@709: typedef PR Prio;
kpeter@709: /// Type of the items stored in the heap.
deba@681: typedef typename ItemIntMap::Key Item;
kpeter@709: /// Type of the item-priority pairs.
deba@681: typedef std::pair<Item,Prio> Pair;
kpeter@709: /// Functor type for comparing the priorities.
deba@683: typedef CMP Compare;
deba@681:
deba@681: private:
deba@683: class Store;
deba@681:
deba@683: std::vector<Store> _data;
deba@683: int _minimum;
deba@683: ItemIntMap &_iim;
deba@683: Compare _comp;
deba@683: int _num;
deba@681:
deba@681: public:
deba@683:
kpeter@709: /// \brief Type to represent the states of the items.
deba@683: ///
kpeter@709: /// Each item has a state associated to it. It can be "in heap",
kpeter@709: /// "pre-heap" or "post-heap". The latter two are indifferent from the
deba@683: /// heap's point of view, but may be useful to the user.
deba@683: ///
deba@683: /// The item-int map must be initialized in such way that it assigns
deba@683: /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
deba@681: enum State {
deba@683: IN_HEAP = 0, ///< = 0.
deba@683: PRE_HEAP = -1, ///< = -1.
deba@683: POST_HEAP = -2 ///< = -2.
deba@681: };
deba@681:
kpeter@709: /// \brief Constructor.
deba@681: ///
kpeter@709: /// Constructor.
kpeter@709: /// \param map A map that assigns \c int values to the items.
kpeter@709: /// It is used internally to handle the cross references.
kpeter@709: /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
deba@683: explicit FibHeap(ItemIntMap &map)
deba@683: : _minimum(0), _iim(map), _num() {}
deba@681:
kpeter@709: /// \brief Constructor.
deba@681: ///
kpeter@709: /// Constructor.
kpeter@709: /// \param map A map that assigns \c int values to the items.
kpeter@709: /// It is used internally to handle the cross references.
kpeter@709: /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
kpeter@709: /// \param comp The function object used for comparing the priorities.
deba@683: FibHeap(ItemIntMap &map, const Compare &comp)
deba@683: : _minimum(0), _iim(map), _comp(comp), _num() {}
deba@681:
deba@681: /// \brief The number of items stored in the heap.
deba@681: ///
kpeter@709: /// This function returns the number of items stored in the heap.
deba@683: int size() const { return _num; }
deba@681:
kpeter@709: /// \brief Check if the heap is empty.
deba@681: ///
kpeter@709: /// This function returns \c true if the heap is empty.
deba@683: bool empty() const { return _num==0; }
deba@681:
kpeter@709: /// \brief Make the heap empty.
deba@681: ///
kpeter@709: /// This functon makes the heap empty.
kpeter@709: /// It does not change the cross reference map. If you want to reuse
kpeter@709: /// a heap that is not surely empty, you should first clear it and
kpeter@709: /// then you should set the cross reference map to \c PRE_HEAP
kpeter@709: /// for each item.
deba@681: void clear() {
deba@683: _data.clear(); _minimum = 0; _num = 0;
deba@681: }
deba@681:
kpeter@709: /// \brief Insert an item into the heap with the given priority.
deba@681: ///
kpeter@709: /// This function inserts the given item into the heap with the
kpeter@709: /// given priority.
kpeter@709: /// \param item The item to insert.
kpeter@709: /// \param prio The priority of the item.
kpeter@709: /// \pre \e item must not be stored in the heap.
kpeter@709: void push (const Item& item, const Prio& prio) {
deba@683: int i=_iim[item];
deba@681: if ( i < 0 ) {
deba@683: int s=_data.size();
deba@683: _iim.set( item, s );
deba@683: Store st;
deba@681: st.name=item;
deba@683: _data.push_back(st);
deba@681: i=s;
deba@681: } else {
deba@683: _data[i].parent=_data[i].child=-1;
deba@683: _data[i].degree=0;
deba@683: _data[i].in=true;
deba@683: _data[i].marked=false;
deba@681: }
deba@681:
deba@683: if ( _num ) {
deba@683: _data[_data[_minimum].right_neighbor].left_neighbor=i;
deba@683: _data[i].right_neighbor=_data[_minimum].right_neighbor;
deba@683: _data[_minimum].right_neighbor=i;
deba@683: _data[i].left_neighbor=_minimum;
kpeter@709: if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
deba@681: } else {
deba@683: _data[i].right_neighbor=_data[i].left_neighbor=i;
deba@683: _minimum=i;
deba@681: }
kpeter@709: _data[i].prio=prio;
deba@683: ++_num;
deba@681: }
deba@681:
kpeter@709: /// \brief Return the item having minimum priority.
deba@681: ///
kpeter@709: /// This function returns the item having minimum priority.
kpeter@709: /// \pre The heap must be non-empty.
deba@683: Item top() const { return _data[_minimum].name; }
deba@681:
kpeter@709: /// \brief The minimum priority.
deba@681: ///
kpeter@709: /// This function returns the minimum priority.
kpeter@709: /// \pre The heap must be non-empty.
kpeter@709: Prio prio() const { return _data[_minimum].prio; }
deba@681:
kpeter@709: /// \brief Remove the item having minimum priority.
deba@681: ///
kpeter@709: /// This function removes the item having minimum priority.
deba@681: /// \pre The heap must be non-empty.
deba@681: void pop() {
deba@681: /*The first case is that there are only one root.*/
deba@683: if ( _data[_minimum].left_neighbor==_minimum ) {
deba@683: _data[_minimum].in=false;
deba@683: if ( _data[_minimum].degree!=0 ) {
kpeter@711: makeRoot(_data[_minimum].child);
deba@683: _minimum=_data[_minimum].child;
deba@681: balance();
deba@681: }
deba@681: } else {
deba@683: int right=_data[_minimum].right_neighbor;
deba@683: unlace(_minimum);
deba@683: _data[_minimum].in=false;
deba@683: if ( _data[_minimum].degree > 0 ) {
deba@683: int left=_data[_minimum].left_neighbor;
deba@683: int child=_data[_minimum].child;
deba@683: int last_child=_data[child].left_neighbor;
deba@681:
kpeter@711: makeRoot(child);
deba@681:
deba@683: _data[left].right_neighbor=child;
deba@683: _data[child].left_neighbor=left;
deba@683: _data[right].left_neighbor=last_child;
deba@683: _data[last_child].right_neighbor=right;
deba@681: }
deba@683: _minimum=right;
deba@681: balance();
deba@681: } // the case where there are more roots
deba@683: --_num;
deba@681: }
deba@681:
kpeter@709: /// \brief Remove the given item from the heap.
deba@681: ///
kpeter@709: /// This function removes the given item from the heap if it is
kpeter@709: /// already stored.
kpeter@709: /// \param item The item to delete.
kpeter@709: /// \pre \e item must be in the heap.
deba@681: void erase (const Item& item) {
deba@683: int i=_iim[item];
deba@681:
deba@683: if ( i >= 0 && _data[i].in ) {
deba@683: if ( _data[i].parent!=-1 ) {
deba@683: int p=_data[i].parent;
deba@681: cut(i,p);
deba@681: cascade(p);
deba@681: }
deba@683: _minimum=i; //As if its prio would be -infinity
deba@681: pop();
deba@681: }
deba@681: }
deba@681:
kpeter@709: /// \brief The priority of the given item.
deba@681: ///
kpeter@709: /// This function returns the priority of the given item.
kpeter@709: /// \param item The item.
kpeter@709: /// \pre \e item must be in the heap.
kpeter@709: Prio operator[](const Item& item) const {
kpeter@709: return _data[_iim[item]].prio;
kpeter@709: }
kpeter@709:
kpeter@709: /// \brief Set the priority of an item or insert it, if it is
kpeter@709: /// not stored in the heap.
kpeter@709: ///
kpeter@709: /// This method sets the priority of the given item if it is
kpeter@709: /// already stored in the heap. Otherwise it inserts the given
kpeter@709: /// item into the heap with the given priority.
kpeter@709: /// \param item The item.
kpeter@709: /// \param prio The priority.
kpeter@709: void set (const Item& item, const Prio& prio) {
deba@683: int i=_iim[item];
kpeter@709: if ( i >= 0 && _data[i].in ) {
kpeter@709: if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
kpeter@709: if ( _comp(_data[i].prio, prio) ) increase(item, prio);
kpeter@709: } else push(item, prio);
kpeter@709: }
kpeter@709:
kpeter@709: /// \brief Decrease the priority of an item to the given value.
kpeter@709: ///
kpeter@709: /// This function decreases the priority of an item to the given value.
kpeter@709: /// \param item The item.
kpeter@709: /// \param prio The priority.
kpeter@709: /// \pre \e item must be stored in the heap with priority at least \e prio.
kpeter@709: void decrease (const Item& item, const Prio& prio) {
kpeter@709: int i=_iim[item];
kpeter@709: _data[i].prio=prio;
deba@683: int p=_data[i].parent;
deba@681:
kpeter@709: if ( p!=-1 && _comp(prio, _data[p].prio) ) {
deba@681: cut(i,p);
deba@681: cascade(p);
deba@681: }
kpeter@709: if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
deba@681: }
deba@681:
kpeter@709: /// \brief Increase the priority of an item to the given value.
deba@681: ///
kpeter@709: /// This function increases the priority of an item to the given value.
kpeter@709: /// \param item The item.
kpeter@709: /// \param prio The priority.
kpeter@709: /// \pre \e item must be stored in the heap with priority at most \e prio.
kpeter@709: void increase (const Item& item, const Prio& prio) {
deba@681: erase(item);
kpeter@709: push(item, prio);
deba@681: }
deba@681:
kpeter@709: /// \brief Return the state of an item.
deba@681: ///
kpeter@709: /// This method returns \c PRE_HEAP if the given item has never
kpeter@709: /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@709: /// and \c POST_HEAP otherwise.
kpeter@709: /// In the latter case it is possible that the item will get back
kpeter@709: /// to the heap again.
kpeter@709: /// \param item The item.
deba@681: State state(const Item &item) const {
deba@683: int i=_iim[item];
deba@681: if( i>=0 ) {
deba@683: if ( _data[i].in ) i=0;
deba@681: else i=-2;
deba@681: }
deba@681: return State(i);
deba@681: }
deba@681:
kpeter@709: /// \brief Set the state of an item in the heap.
deba@681: ///
kpeter@709: /// This function sets the state of the given item in the heap.
kpeter@709: /// It can be used to manually clear the heap when it is important
kpeter@709: /// to achive better time complexity.
deba@681: /// \param i The item.
deba@681: /// \param st The state. It should not be \c IN_HEAP.
deba@681: void state(const Item& i, State st) {
deba@681: switch (st) {
deba@681: case POST_HEAP:
deba@681: case PRE_HEAP:
deba@681: if (state(i) == IN_HEAP) {
deba@681: erase(i);
deba@681: }
deba@683: _iim[i] = st;
deba@681: break;
deba@681: case IN_HEAP:
deba@681: break;
deba@681: }
deba@681: }
deba@681:
deba@681: private:
deba@681:
deba@681: void balance() {
deba@681:
deba@683: int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
deba@681:
deba@681: std::vector<int> A(maxdeg,-1);
deba@681:
deba@681: /*
deba@681: *Recall that now minimum does not point to the minimum prio element.
deba@681: *We set minimum to this during balance().
deba@681: */
deba@683: int anchor=_data[_minimum].left_neighbor;
deba@683: int next=_minimum;
deba@681: bool end=false;
deba@681:
deba@681: do {
deba@681: int active=next;
deba@681: if ( anchor==active ) end=true;
deba@683: int d=_data[active].degree;
deba@683: next=_data[active].right_neighbor;
deba@681:
deba@681: while (A[d]!=-1) {
deba@683: if( _comp(_data[active].prio, _data[A[d]].prio) ) {
deba@681: fuse(active,A[d]);
deba@681: } else {
deba@681: fuse(A[d],active);
deba@681: active=A[d];
deba@681: }
deba@681: A[d]=-1;
deba@681: ++d;
deba@681: }
deba@681: A[d]=active;
deba@681: } while ( !end );
deba@681:
deba@681:
deba@683: while ( _data[_minimum].parent >=0 )
deba@683: _minimum=_data[_minimum].parent;
deba@683: int s=_minimum;
deba@683: int m=_minimum;
deba@681: do {
deba@683: if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
deba@683: s=_data[s].right_neighbor;
deba@681: } while ( s != m );
deba@681: }
deba@681:
kpeter@711: void makeRoot(int c) {
deba@681: int s=c;
deba@681: do {
deba@683: _data[s].parent=-1;
deba@683: s=_data[s].right_neighbor;
deba@681: } while ( s != c );
deba@681: }
deba@681:
deba@681: void cut(int a, int b) {
deba@681: /*
deba@681: *Replacing a from the children of b.
deba@681: */
deba@683: --_data[b].degree;
deba@681:
deba@683: if ( _data[b].degree !=0 ) {
deba@683: int child=_data[b].child;
deba@681: if ( child==a )
deba@683: _data[b].child=_data[child].right_neighbor;
deba@681: unlace(a);
deba@681: }
deba@681:
deba@681:
deba@681: /*Lacing a to the roots.*/
deba@683: int right=_data[_minimum].right_neighbor;
deba@683: _data[_minimum].right_neighbor=a;
deba@683: _data[a].left_neighbor=_minimum;
deba@683: _data[a].right_neighbor=right;
deba@683: _data[right].left_neighbor=a;
deba@681:
deba@683: _data[a].parent=-1;
deba@683: _data[a].marked=false;
deba@681: }
deba@681:
deba@681: void cascade(int a) {
deba@683: if ( _data[a].parent!=-1 ) {
deba@683: int p=_data[a].parent;
deba@681:
deba@683: if ( _data[a].marked==false ) _data[a].marked=true;
deba@681: else {
deba@681: cut(a,p);
deba@681: cascade(p);
deba@681: }
deba@681: }
deba@681: }
deba@681:
deba@681: void fuse(int a, int b) {
deba@681: unlace(b);
deba@681:
deba@681: /*Lacing b under a.*/
deba@683: _data[b].parent=a;
deba@681:
deba@683: if (_data[a].degree==0) {
deba@683: _data[b].left_neighbor=b;
deba@683: _data[b].right_neighbor=b;
deba@683: _data[a].child=b;
deba@681: } else {
deba@683: int child=_data[a].child;
deba@683: int last_child=_data[child].left_neighbor;
deba@683: _data[child].left_neighbor=b;
deba@683: _data[b].right_neighbor=child;
deba@683: _data[last_child].right_neighbor=b;
deba@683: _data[b].left_neighbor=last_child;
deba@681: }
deba@681:
deba@683: ++_data[a].degree;
deba@681:
deba@683: _data[b].marked=false;
deba@681: }
deba@681:
deba@681: /*
deba@681: *It is invoked only if a has siblings.
deba@681: */
deba@681: void unlace(int a) {
deba@683: int leftn=_data[a].left_neighbor;
deba@683: int rightn=_data[a].right_neighbor;
deba@683: _data[leftn].right_neighbor=rightn;
deba@683: _data[rightn].left_neighbor=leftn;
deba@681: }
deba@681:
deba@681:
deba@683: class Store {
deba@681: friend class FibHeap;
deba@681:
deba@681: Item name;
deba@681: int parent;
deba@681: int left_neighbor;
deba@681: int right_neighbor;
deba@681: int child;
deba@681: int degree;
deba@681: bool marked;
deba@681: bool in;
deba@681: Prio prio;
deba@681:
deba@683: Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
deba@681: };
deba@681: };
deba@681:
deba@681: } //namespace lemon
deba@681:
deba@681: #endif //LEMON_FIB_HEAP_H
deba@681: