lemon/binomial_heap.h
changeset 875 07ec2b52e53d
parent 707 3887d6f994d7
child 877 141f9c0db4a3
equal deleted inserted replaced
2:847a7cba7470 0:b036ebcfd839
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #ifndef LEMON_BINOM_HEAP_H
    19 #ifndef LEMON_BINOMIAL_HEAP_H
    20 #define LEMON_BINOM_HEAP_H
    20 #define LEMON_BINOMIAL_HEAP_H
    21 
    21 
    22 ///\file
    22 ///\file
    23 ///\ingroup heaps
    23 ///\ingroup heaps
    24 ///\brief Binomial Heap implementation.
    24 ///\brief Binomial Heap implementation.
    25 
    25 
    51 #ifdef DOXYGEN
    51 #ifdef DOXYGEN
    52   template <typename PR, typename IM, typename CMP>
    52   template <typename PR, typename IM, typename CMP>
    53 #else
    53 #else
    54   template <typename PR, typename IM, typename CMP = std::less<PR> >
    54   template <typename PR, typename IM, typename CMP = std::less<PR> >
    55 #endif
    55 #endif
    56   class BinomHeap {
    56   class BinomialHeap {
    57   public:
    57   public:
    58     /// Type of the item-int map.
    58     /// Type of the item-int map.
    59     typedef IM ItemIntMap;
    59     typedef IM ItemIntMap;
    60     /// Type of the priorities.
    60     /// Type of the priorities.
    61     typedef PR Prio;
    61     typedef PR Prio;
    92     ///
    92     ///
    93     /// Constructor.
    93     /// Constructor.
    94     /// \param map A map that assigns \c int values to the items.
    94     /// \param map A map that assigns \c int values to the items.
    95     /// It is used internally to handle the cross references.
    95     /// It is used internally to handle the cross references.
    96     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    96     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    97     explicit BinomHeap(ItemIntMap &map)
    97     explicit BinomialHeap(ItemIntMap &map)
    98       : _min(0), _head(-1), _iim(map), _num_items(0) {}
    98       : _min(0), _head(-1), _iim(map), _num_items(0) {}
    99 
    99 
   100     /// \brief Constructor.
   100     /// \brief Constructor.
   101     ///
   101     ///
   102     /// Constructor.
   102     /// Constructor.
   103     /// \param map A map that assigns \c int values to the items.
   103     /// \param map A map that assigns \c int values to the items.
   104     /// It is used internally to handle the cross references.
   104     /// It is used internally to handle the cross references.
   105     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   105     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   106     /// \param comp The function object used for comparing the priorities.
   106     /// \param comp The function object used for comparing the priorities.
   107     BinomHeap(ItemIntMap &map, const Compare &comp)
   107     BinomialHeap(ItemIntMap &map, const Compare &comp)
   108       : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   108       : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
   109 
   109 
   110     /// \brief The number of items stored in the heap.
   110     /// \brief The number of items stored in the heap.
   111     ///
   111     ///
   112     /// This function returns the number of items stored in the heap.
   112     /// This function returns the number of items stored in the heap.
   422     }
   422     }
   423 
   423 
   424   private:
   424   private:
   425 
   425 
   426     class Store {
   426     class Store {
   427       friend class BinomHeap;
   427       friend class BinomialHeap;
   428 
   428 
   429       Item name;
   429       Item name;
   430       int parent;
   430       int parent;
   431       int right_neighbor;
   431       int right_neighbor;
   432       int child;
   432       int child;
   439     };
   439     };
   440   };
   440   };
   441 
   441 
   442 } //namespace lemon
   442 } //namespace lemon
   443 
   443 
   444 #endif //LEMON_BINOM_HEAP_H
   444 #endif //LEMON_BINOMIAL_HEAP_H
   445 
   445