Changeset 855:65a0521e744e in lemon-main for lemon/dheap.h
- Timestamp:
- 09/29/09 13:32:01 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
lemon/dheap.h
r706 r855 17 17 */ 18 18 19 #ifndef LEMON_ KARY_HEAP_H20 #define LEMON_ KARY_HEAP_H19 #ifndef LEMON_DHEAP_H 20 #define LEMON_DHEAP_H 21 21 22 22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Fourary heap implementation.24 ///\brief D-ary heap implementation. 25 25 26 26 #include <vector> … … 32 32 /// \ingroup heaps 33 33 /// 34 ///\brief K-ary heap data structure.35 /// 36 /// This class implements the \e K-ary \e heap data structure.34 ///\brief D-ary heap data structure. 35 /// 36 /// This class implements the \e D-ary \e heap data structure. 37 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 38 38 /// 39 /// The \ref KaryHeap "K-ary heap" is a generalization of the39 /// The \ref DHeap "D-ary heap" is a generalization of the 40 40 /// \ref BinHeap "binary heap" structure, its nodes have at most 41 /// \c Kchildren, instead of two.42 /// \ref BinHeap and \ref FouraryHeap are specialized implementations43 /// of this structure for <tt> K=2</tt> and <tt>K=4</tt>, respectively.41 /// \c D children, instead of two. 42 /// \ref BinHeap and \ref QuadHeap are specialized implementations 43 /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively. 44 44 /// 45 45 /// \tparam PR Type of the priorities of the items. 46 46 /// \tparam IM A read-writable item map with \c int values, used 47 47 /// internally to handle the cross references. 48 /// \tparam K The degree of the heap, each node have at most \e K48 /// \tparam D The degree of the heap, each node have at most \e D 49 49 /// children. The default is 16. Powers of two are suggested to use 50 50 /// so that the multiplications and divisions needed to traverse the … … 56 56 ///\sa FouraryHeap 57 57 #ifdef DOXYGEN 58 template <typename PR, typename IM, int K, typename CMP>58 template <typename PR, typename IM, int D, typename CMP> 59 59 #else 60 template <typename PR, typename IM, int K= 16,60 template <typename PR, typename IM, int D = 16, 61 61 typename CMP = std::less<PR> > 62 62 #endif 63 class KaryHeap {63 class DHeap { 64 64 public: 65 65 /// Type of the item-int map. … … 100 100 /// It is used internally to handle the cross references. 101 101 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 102 explicit KaryHeap(ItemIntMap &map) : _iim(map) {}102 explicit DHeap(ItemIntMap &map) : _iim(map) {} 103 103 104 104 /// \brief Constructor. … … 109 109 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 110 110 /// \param comp The function object used for comparing the priorities. 111 KaryHeap(ItemIntMap &map, const Compare &comp)111 DHeap(ItemIntMap &map, const Compare &comp) 112 112 : _iim(map), _comp(comp) {} 113 113 … … 132 132 133 133 private: 134 int parent(int i) { return (i-1)/ K; }135 int firstChild(int i) { return K*i+1; }134 int parent(int i) { return (i-1)/D; } 135 int firstChild(int i) { return D*i+1; } 136 136 137 137 bool less(const Pair &p1, const Pair &p2) const { … … 152 152 if( length>1 ) { 153 153 int child = firstChild(hole); 154 while( child+ K<=length ) {154 while( child+D<=length ) { 155 155 int min=child; 156 for (int i=1; i< K; ++i) {156 for (int i=1; i<D; ++i) { 157 157 if( less(_data[child+i], _data[min]) ) 158 158 min=child+i; … … 346 346 } 347 347 348 }; // class KaryHeap348 }; // class DHeap 349 349 350 350 } // namespace lemon 351 351 352 #endif // LEMON_ KARY_HEAP_H352 #endif // LEMON_DHEAP_H
Note: See TracChangeset
for help on using the changeset viewer.