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 |