Changeset 855:65a0521e744e in lemon-main for lemon/dheap.h

Timestamp:

09/29/09 13:32:01 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Rename heap structures (#301)

• KaryHeap? --> DHeap
• FouraryHeap? --> QuadHeap?
• BinomHeap? --> BinomialHeap?

File:

• lemon/dheap.h (moved) (moved from lemon/kary_heap.h) (8 diffs)

lemon/dheap.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_KARY_HEAP_H
-#define LEMON_KARY_HEAP_H
+#ifndef LEMON_DHEAP_H
+#define LEMON_DHEAP_H
 
 ///\ingroup heaps
 ///\file
-///\brief Fourary heap implementation.
+///\brief D-ary heap implementation.
 
 #include <vector>
@@ -32 +32 @@
   /// \ingroup heaps
   ///
-  ///\brief K-ary heap data structure.
-  ///
-  /// This class implements the \e K-ary \e heap data structure.
+  ///\brief D-ary heap data structure.
+  ///
+  /// This class implements the \e D-ary \e heap data structure.
   /// It fully conforms to the \ref concepts::Heap "heap concept".
   ///
-  /// The \ref KaryHeap "K-ary heap" is a generalization of the
+  /// The \ref DHeap "D-ary heap" is a generalization of the
   /// \ref BinHeap "binary heap" structure, its nodes have at most
-  /// \c K children, instead of two.
-  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
-  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
+  /// \c D children, instead of two.
+  /// \ref BinHeap and \ref QuadHeap are specialized implementations
+  /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively.
   ///
   /// \tparam PR Type of the priorities of the items.
   /// \tparam IM A read-writable item map with \c int values, used
   /// internally to handle the cross references.
-  /// \tparam K The degree of the heap, each node have at most \e K
+  /// \tparam D The degree of the heap, each node have at most \e D
   /// children. The default is 16. Powers of two are suggested to use
   /// so that the multiplications and divisions needed to traverse the
@@ -56 +56 @@
   ///\sa FouraryHeap
 #ifdef DOXYGEN
-  template <typename PR, typename IM, int K, typename CMP>
+  template <typename PR, typename IM, int D, typename CMP>
 #else
-  template <typename PR, typename IM, int K = 16,
+  template <typename PR, typename IM, int D = 16,
             typename CMP = std::less<PR> >
 #endif
-  class KaryHeap {
+  class DHeap {
   public:
     /// Type of the item-int map.
@@ -100 +100 @@
     /// It is used internally to handle the cross references.
     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-    explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
+    explicit DHeap(ItemIntMap &map) : _iim(map) {}
 
     /// \brief Constructor.
@@ -109 +109 @@
     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     /// \param comp The function object used for comparing the priorities.
-    KaryHeap(ItemIntMap &map, const Compare &comp)
+    DHeap(ItemIntMap &map, const Compare &comp)
       : _iim(map), _comp(comp) {}
 
@@ -132 +132 @@
 
   private:
-    int parent(int i) { return (i-1)/K; }
-    int firstChild(int i) { return K*i+1; }
+    int parent(int i) { return (i-1)/D; }
+    int firstChild(int i) { return D*i+1; }
 
     bool less(const Pair &p1, const Pair &p2) const {
@@ -152 +152 @@
       if( length>1 ) {
         int child = firstChild(hole);
-        while( child+K<=length ) {
+        while( child+D<=length ) {
           int min=child;
-          for (int i=1; i<K; ++i) {
+          for (int i=1; i<D; ++i) {
             if( less(_data[child+i], _data[min]) )
               min=child+i;
@@ -346 +346 @@
     }
 
-  }; // class KaryHeap
+  }; // class DHeap
 
 } // namespace lemon
 
-#endif // LEMON_KARY_HEAP_H
+#endif // LEMON_DHEAP_H