kpeter@701: /* -*- C++ -*- kpeter@701: * kpeter@701: * This file is a part of LEMON, a generic C++ optimization library kpeter@701: * kpeter@701: * Copyright (C) 2003-2008 kpeter@701: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@701: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@701: * kpeter@701: * Permission to use, modify and distribute this software is granted kpeter@701: * provided that this copyright notice appears in all copies. For kpeter@701: * precise terms see the accompanying LICENSE file. kpeter@701: * kpeter@701: * This software is provided "AS IS" with no warranty of any kind, kpeter@701: * express or implied, and with no claim as to its suitability for any kpeter@701: * purpose. kpeter@701: * kpeter@701: */ kpeter@701: kpeter@701: #ifndef LEMON_PAIRING_HEAP_H kpeter@701: #define LEMON_PAIRING_HEAP_H kpeter@701: kpeter@701: ///\file kpeter@701: ///\ingroup auxdat kpeter@701: ///\brief Pairing Heap implementation. kpeter@701: kpeter@701: #include kpeter@701: #include kpeter@701: #include kpeter@701: kpeter@701: namespace lemon { kpeter@701: kpeter@701: /// \ingroup auxdat kpeter@701: /// kpeter@701: ///\brief Pairing Heap. kpeter@701: /// kpeter@701: ///This class implements the \e Pairing \e heap data structure. A \e heap kpeter@701: ///is a data structure for storing items with specified values called \e kpeter@701: ///priorities in such a way that finding the item with minimum priority is kpeter@701: ///efficient. \c Compare specifies the ordering of the priorities. In a heap kpeter@701: ///one can change the priority of an item, add or erase an item, etc. kpeter@701: /// kpeter@701: ///The methods \ref increase and \ref erase are not efficient in a Pairing kpeter@701: ///heap. In case of many calls to these operations, it is better to use a kpeter@701: ///\ref BinHeap "binary heap". kpeter@701: /// kpeter@701: ///\param _Prio Type of the priority of the items. kpeter@701: ///\param _ItemIntMap A read and writable Item int map, used internally kpeter@701: ///to handle the cross references. kpeter@701: ///\param _Compare A class for the ordering of the priorities. The kpeter@701: ///default is \c std::less<_Prio>. kpeter@701: /// kpeter@701: ///\sa BinHeap kpeter@701: ///\sa Dijkstra kpeter@701: ///\author Dorian Batha kpeter@701: kpeter@701: #ifdef DOXYGEN kpeter@701: template kpeter@701: #else kpeter@701: template > kpeter@701: #endif kpeter@701: class PairingHeap { kpeter@701: public: kpeter@701: typedef _ItemIntMap ItemIntMap; kpeter@701: typedef _Prio Prio; kpeter@701: typedef typename ItemIntMap::Key Item; kpeter@701: typedef std::pair Pair; kpeter@701: typedef _Compare Compare; kpeter@701: kpeter@701: private: kpeter@701: class store; kpeter@701: kpeter@701: std::vector container; kpeter@701: int minimum; kpeter@701: ItemIntMap &iimap; kpeter@701: Compare comp; kpeter@701: int num_items; kpeter@701: kpeter@701: public: kpeter@701: ///Status of the nodes kpeter@701: enum State { kpeter@701: ///The node is in the heap kpeter@701: IN_HEAP = 0, kpeter@701: ///The node has never been in the heap kpeter@701: PRE_HEAP = -1, kpeter@701: ///The node was in the heap but it got out of it kpeter@701: POST_HEAP = -2 kpeter@701: }; kpeter@701: kpeter@701: /// \brief The constructor kpeter@701: /// kpeter@701: /// \c _iimap should be given to the constructor, since it is kpeter@701: /// used internally to handle the cross references. kpeter@701: explicit PairingHeap(ItemIntMap &_iimap) kpeter@701: : minimum(0), iimap(_iimap), num_items(0) {} kpeter@701: kpeter@701: /// \brief The constructor kpeter@701: /// kpeter@701: /// \c _iimap should be given to the constructor, since it is used kpeter@701: /// internally to handle the cross references. \c _comp is an kpeter@701: /// object for ordering of the priorities. kpeter@701: PairingHeap(ItemIntMap &_iimap, const Compare &_comp) kpeter@701: : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {} kpeter@701: kpeter@701: /// \brief The number of items stored in the heap. kpeter@701: /// kpeter@701: /// Returns the number of items stored in the heap. kpeter@701: int size() const { return num_items; } kpeter@701: kpeter@701: /// \brief Checks if the heap stores no items. kpeter@701: /// kpeter@701: /// Returns \c true if and only if the heap stores no items. kpeter@701: bool empty() const { return num_items==0; } kpeter@701: kpeter@701: /// \brief Make empty this heap. kpeter@701: /// kpeter@701: /// Make empty this heap. It does not change the cross reference kpeter@701: /// map. If you want to reuse a heap what is not surely empty you kpeter@701: /// should first clear the heap and after that you should set the kpeter@701: /// cross reference map for each item to \c PRE_HEAP. kpeter@701: void clear() { kpeter@701: container.clear(); kpeter@701: minimum = 0; kpeter@701: num_items = 0; kpeter@701: } kpeter@701: kpeter@701: /// \brief \c item gets to the heap with priority \c value independently kpeter@701: /// if \c item was already there. kpeter@701: /// kpeter@701: /// This method calls \ref push(\c item, \c value) if \c item is not kpeter@701: /// stored in the heap and it calls \ref decrease(\c item, \c value) or kpeter@701: /// \ref increase(\c item, \c value) otherwise. kpeter@701: void set (const Item& item, const Prio& value) { kpeter@701: int i=iimap[item]; kpeter@701: if ( i>=0 && container[i].in ) { kpeter@701: if ( comp(value, container[i].prio) ) decrease(item, value); kpeter@701: if ( comp(container[i].prio, value) ) increase(item, value); kpeter@701: } else push(item, value); kpeter@701: } kpeter@701: kpeter@701: /// \brief Adds \c item to the heap with priority \c value. kpeter@701: /// kpeter@701: /// Adds \c item to the heap with priority \c value. kpeter@701: /// \pre \c item must not be stored in the heap. kpeter@701: void push (const Item& item, const Prio& value) { kpeter@701: int i=iimap[item]; kpeter@701: if( i<0 ) { kpeter@701: int s=container.size(); kpeter@701: iimap.set(item, s); kpeter@701: store st; kpeter@701: st.name=item; kpeter@701: container.push_back(st); kpeter@701: i=s; kpeter@701: } else { kpeter@701: container[i].parent=container[i].child=-1; kpeter@701: container[i].left_child=false; kpeter@701: container[i].degree=0; kpeter@701: container[i].in=true; kpeter@701: } kpeter@701: kpeter@701: container[i].prio=value; kpeter@701: kpeter@701: if ( num_items!=0 ) { kpeter@701: if ( comp( value, container[minimum].prio) ) { kpeter@701: fuse(i,minimum); kpeter@701: minimum=i; kpeter@701: } kpeter@701: else fuse(minimum,i); kpeter@701: } kpeter@701: else minimum=i; kpeter@701: kpeter@701: ++num_items; kpeter@701: } kpeter@701: kpeter@701: /// \brief Returns the item with minimum priority relative to \c Compare. kpeter@701: /// kpeter@701: /// This method returns the item with minimum priority relative to \c kpeter@701: /// Compare. kpeter@701: /// \pre The heap must be nonempty. kpeter@701: Item top() const { return container[minimum].name; } kpeter@701: kpeter@701: /// \brief Returns the minimum priority relative to \c Compare. kpeter@701: /// kpeter@701: /// It returns the minimum priority relative to \c Compare. kpeter@701: /// \pre The heap must be nonempty. kpeter@701: const Prio& prio() const { return container[minimum].prio; } kpeter@701: kpeter@701: /// \brief Returns the priority of \c item. kpeter@701: /// kpeter@701: /// It returns the priority of \c item. kpeter@701: /// \pre \c item must be in the heap. kpeter@701: const Prio& operator[](const Item& item) const { kpeter@701: return container[iimap[item]].prio; kpeter@701: } kpeter@701: kpeter@701: /// \brief Deletes the item with minimum priority relative to \c Compare. kpeter@701: /// kpeter@701: /// This method deletes the item with minimum priority relative to \c kpeter@701: /// Compare from the heap. kpeter@701: /// \pre The heap must be non-empty. kpeter@701: void pop() { kpeter@701: int TreeArray[num_items]; kpeter@701: int i=0, num_child=0, child_right = 0; kpeter@701: container[minimum].in=false; kpeter@701: kpeter@701: if( -1!=container[minimum].child ) { kpeter@701: i=container[minimum].child; kpeter@701: TreeArray[num_child] = i; kpeter@701: container[i].parent = -1; kpeter@701: container[minimum].child = -1; kpeter@701: kpeter@701: ++num_child; kpeter@701: int ch=-1; kpeter@701: while( container[i].child!=-1 ) { kpeter@701: ch=container[i].child; kpeter@701: if( container[ch].left_child && i==container[ch].parent ) { kpeter@701: i=ch; kpeter@701: //break; kpeter@701: } else { kpeter@701: if( container[ch].left_child ) { kpeter@701: child_right=container[ch].parent; kpeter@701: container[ch].parent = i; kpeter@701: --container[i].degree; kpeter@701: } kpeter@701: else { kpeter@701: child_right=ch; kpeter@701: container[i].child=-1; kpeter@701: container[i].degree=0; kpeter@701: } kpeter@701: container[child_right].parent = -1; kpeter@701: TreeArray[num_child] = child_right; kpeter@701: i = child_right; kpeter@701: ++num_child; kpeter@701: } kpeter@701: } kpeter@701: kpeter@701: int other; kpeter@701: for( i=0; i=2) { kpeter@701: if ( comp(container[TreeArray[i]].prio, kpeter@701: container[TreeArray[i-2]].prio) ) { kpeter@701: other=TreeArray[i]; kpeter@701: TreeArray[i]=TreeArray[i-2]; kpeter@701: TreeArray[i-2]=other; kpeter@701: } kpeter@701: fuse( TreeArray[i-2], TreeArray[i] ); kpeter@701: i-=2; kpeter@701: } kpeter@701: minimum = TreeArray[0]; kpeter@701: } kpeter@701: kpeter@701: if ( 0==num_child ) { kpeter@701: minimum = container[minimum].child; kpeter@701: } kpeter@701: kpeter@702: if (minimum >= 0) container[minimum].left_child = false; kpeter@702: kpeter@701: --num_items; kpeter@701: } kpeter@701: kpeter@701: /// \brief Deletes \c item from the heap. kpeter@701: /// kpeter@701: /// This method deletes \c item from the heap, if \c item was already kpeter@701: /// stored in the heap. It is quite inefficient in Pairing heaps. kpeter@701: void erase (const Item& item) { kpeter@701: int i=iimap[item]; kpeter@701: if ( i>=0 && container[i].in ) { kpeter@701: decrease( item, container[minimum].prio-1 ); kpeter@701: pop(); kpeter@701: } kpeter@701: } kpeter@701: kpeter@701: /// \brief Decreases the priority of \c item to \c value. kpeter@701: /// kpeter@701: /// This method decreases the priority of \c item to \c value. kpeter@701: /// \pre \c item must be stored in the heap with priority at least \c kpeter@701: /// value relative to \c Compare. kpeter@701: void decrease (Item item, const Prio& value) { kpeter@701: int i=iimap[item]; kpeter@701: container[i].prio=value; kpeter@701: int p=container[i].parent; kpeter@701: kpeter@701: if( container[i].left_child && i!=container[p].child ) { kpeter@701: p=container[p].parent; kpeter@701: } kpeter@701: kpeter@701: if ( p!=-1 && comp(value,container[p].prio) ) { kpeter@701: cut(i,p); kpeter@701: if ( comp(container[minimum].prio,value) ) { kpeter@701: fuse(minimum,i); kpeter@701: } else { kpeter@701: fuse(i,minimum); kpeter@701: minimum=i; kpeter@701: } kpeter@701: } kpeter@701: } kpeter@701: kpeter@701: /// \brief Increases the priority of \c item to \c value. kpeter@701: /// kpeter@701: /// This method sets the priority of \c item to \c value. Though kpeter@701: /// there is no precondition on the priority of \c item, this kpeter@701: /// method should be used only if it is indeed necessary to increase kpeter@701: /// (relative to \c Compare) the priority of \c item, because this kpeter@701: /// method is inefficient. kpeter@701: void increase (Item item, const Prio& value) { kpeter@701: erase(item); kpeter@701: push(item,value); kpeter@701: } kpeter@701: kpeter@701: /// \brief Returns if \c item is in, has already been in, or has never kpeter@701: /// been in the heap. kpeter@701: /// kpeter@701: /// This method returns PRE_HEAP if \c item has never been in the kpeter@701: /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP kpeter@701: /// otherwise. In the latter case it is possible that \c item will kpeter@701: /// get back to the heap again. kpeter@701: State state(const Item &item) const { kpeter@701: int i=iimap[item]; kpeter@701: if( i>=0 ) { kpeter@701: if( container[i].in ) i=0; kpeter@701: else i=-2; kpeter@701: } kpeter@701: return State(i); kpeter@701: } kpeter@701: kpeter@701: /// \brief Sets the state of the \c item in the heap. kpeter@701: /// kpeter@701: /// Sets the state of the \c item in the heap. It can be used to kpeter@701: /// manually clear the heap when it is important to achive the kpeter@701: /// better time complexity. kpeter@701: /// \param i The item. kpeter@701: /// \param st The state. It should not be \c IN_HEAP. kpeter@701: void state(const Item& i, State st) { kpeter@701: switch (st) { kpeter@701: case POST_HEAP: kpeter@701: case PRE_HEAP: kpeter@701: if (state(i) == IN_HEAP) erase(i); kpeter@701: iimap[i]=st; kpeter@701: break; kpeter@701: case IN_HEAP: kpeter@701: break; kpeter@701: } kpeter@701: } kpeter@701: kpeter@701: private: kpeter@701: kpeter@701: void cut(int a, int b) { kpeter@701: int child_a; kpeter@701: switch (container[a].degree) { kpeter@701: case 2: kpeter@701: child_a = container[container[a].child].parent; kpeter@701: if( container[a].left_child ) { kpeter@701: container[child_a].left_child=true; kpeter@701: container[b].child=child_a; kpeter@701: container[child_a].parent=container[a].parent; kpeter@701: } kpeter@701: else { kpeter@701: container[child_a].left_child=false; kpeter@701: container[child_a].parent=b; kpeter@701: if( a!=container[b].child ) kpeter@701: container[container[b].child].parent=child_a; kpeter@701: else kpeter@701: container[b].child=child_a; kpeter@701: } kpeter@701: --container[a].degree; kpeter@701: container[container[a].child].parent=a; kpeter@701: break; kpeter@701: kpeter@701: case 1: kpeter@701: child_a = container[a].child; kpeter@701: if( !container[child_a].left_child ) { kpeter@701: --container[a].degree; kpeter@701: if( container[a].left_child ) { kpeter@701: container[child_a].left_child=true; kpeter@701: container[child_a].parent=container[a].parent; kpeter@701: container[b].child=child_a; kpeter@701: } kpeter@701: else { kpeter@701: container[child_a].left_child=false; kpeter@701: container[child_a].parent=b; kpeter@701: if( a!=container[b].child ) kpeter@701: container[container[b].child].parent=child_a; kpeter@701: else kpeter@701: container[b].child=child_a; kpeter@701: } kpeter@701: container[a].child=-1; kpeter@701: } kpeter@701: else { kpeter@701: --container[b].degree; kpeter@701: if( container[a].left_child ) { kpeter@701: container[b].child = kpeter@701: (1==container[b].degree) ? container[a].parent : -1; kpeter@701: } else { kpeter@701: if (1==container[b].degree) kpeter@701: container[container[b].child].parent=b; kpeter@701: else kpeter@701: container[b].child=-1; kpeter@701: } kpeter@701: } kpeter@701: break; kpeter@701: kpeter@701: case 0: kpeter@701: --container[b].degree; kpeter@701: if( container[a].left_child ) { kpeter@701: container[b].child = kpeter@701: (0!=container[b].degree) ? container[a].parent : -1; kpeter@701: } else { kpeter@701: if( 0!=container[b].degree ) kpeter@701: container[container[b].child].parent=b; kpeter@701: else kpeter@701: container[b].child=-1; kpeter@701: } kpeter@701: break; kpeter@701: } kpeter@701: container[a].parent=-1; kpeter@701: container[a].left_child=false; kpeter@701: } kpeter@701: kpeter@701: void fuse(int a, int b) { kpeter@701: int child_a = container[a].child; kpeter@701: int child_b = container[b].child; kpeter@701: container[a].child=b; kpeter@701: container[b].parent=a; kpeter@701: container[b].left_child=true; kpeter@701: kpeter@701: if( -1!=child_a ) { kpeter@701: container[b].child=child_a; kpeter@701: container[child_a].parent=b; kpeter@701: container[child_a].left_child=false; kpeter@701: ++container[b].degree; kpeter@701: kpeter@701: if( -1!=child_b ) { kpeter@701: container[b].child=child_b; kpeter@701: container[child_b].parent=child_a; kpeter@701: } kpeter@701: } kpeter@701: else { ++container[a].degree; } kpeter@701: } kpeter@701: kpeter@701: class store { kpeter@701: friend class PairingHeap; kpeter@701: kpeter@701: Item name; kpeter@701: int parent; kpeter@701: int child; kpeter@701: bool left_child; kpeter@701: int degree; kpeter@701: bool in; kpeter@701: Prio prio; kpeter@701: kpeter@701: store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {} kpeter@701: }; kpeter@701: }; kpeter@701: kpeter@701: } //namespace lemon kpeter@701: kpeter@701: #endif //LEMON_PAIRING_HEAP_H kpeter@701: