lemon/bin_heap.h
changeset 738 456fa5bc3256
parent 584 33c6b6e755cd
child 709 0747f332c478
equal deleted inserted replaced
5:3f9c26b7726f 6:4cb040b09d6e
    31 
    31 
    32   ///\ingroup auxdat
    32   ///\ingroup auxdat
    33   ///
    33   ///
    34   ///\brief A Binary Heap implementation.
    34   ///\brief A Binary Heap implementation.
    35   ///
    35   ///
    36   ///This class implements the \e binary \e heap data structure. 
    36   ///This class implements the \e binary \e heap data structure.
    37   /// 
    37   ///
    38   ///A \e heap is a data structure for storing items with specified values
    38   ///A \e heap is a data structure for storing items with specified values
    39   ///called \e priorities in such a way that finding the item with minimum
    39   ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c Comp specifies the ordering of the priorities.
    40   ///priority is efficient. \c CMP specifies the ordering of the priorities.
    41   ///In a heap one can change the priority of an item, add or erase an
    41   ///In a heap one can change the priority of an item, add or erase an
    42   ///item, etc.
    42   ///item, etc.
    43   ///
    43   ///
    44   ///\tparam PR Type of the priority of the items.
    44   ///\tparam PR Type of the priority of the items.
    45   ///\tparam IM A read and writable item map with int values, used internally
    45   ///\tparam IM A read and writable item map with int values, used internally
    46   ///to handle the cross references.
    46   ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
    47   ///\tparam CMP A functor class for the ordering of the priorities.
    48   ///The default is \c std::less<PR>.
    48   ///The default is \c std::less<PR>.
    49   ///
    49   ///
    50   ///\sa FibHeap
    50   ///\sa FibHeap
    51   ///\sa Dijkstra
    51   ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
    52   template <typename PR, typename IM, typename CMP = std::less<PR> >
    53   class BinHeap {
    53   class BinHeap {
    54 
    54 
    55   public:
    55   public:
    56     ///\e
    56     ///\e
    57     typedef IM ItemIntMap;
    57     typedef IM ItemIntMap;
    60     ///\e
    60     ///\e
    61     typedef typename ItemIntMap::Key Item;
    61     typedef typename ItemIntMap::Key Item;
    62     ///\e
    62     ///\e
    63     typedef std::pair<Item,Prio> Pair;
    63     typedef std::pair<Item,Prio> Pair;
    64     ///\e
    64     ///\e
    65     typedef Comp Compare;
    65     typedef CMP Compare;
    66 
    66 
    67     /// \brief Type to represent the items states.
    67     /// \brief Type to represent the items states.
    68     ///
    68     ///
    69     /// Each Item element have a state associated to it. It may be "in heap",
    69     /// Each Item element have a state associated to it. It may be "in heap",
    70     /// "pre heap" or "post heap". The latter two are indifferent from the
    70     /// "pre heap" or "post heap". The latter two are indifferent from the