COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
09/29/09 13:32:01 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rename heap structures (#301)

File:
1 moved

Legend:

Unmodified
Added
Removed
  • lemon/dheap.h

    r706 r855  
    1717 */
    1818
    19 #ifndef LEMON_KARY_HEAP_H
    20 #define LEMON_KARY_HEAP_H
     19#ifndef LEMON_DHEAP_H
     20#define LEMON_DHEAP_H
    2121
    2222///\ingroup heaps
    2323///\file
    24 ///\brief Fourary heap implementation.
     24///\brief D-ary heap implementation.
    2525
    2626#include <vector>
     
    3232  /// \ingroup heaps
    3333  ///
    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.
    3737  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3838  ///
    39   /// The \ref KaryHeap "K-ary heap" is a generalization of the
     39  /// The \ref DHeap "D-ary heap" is a generalization of the
    4040  /// \ref BinHeap "binary heap" structure, its nodes have at most
    41   /// \c K children, instead of two.
    42   /// \ref BinHeap and \ref FouraryHeap are specialized implementations
    43   /// 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.
    4444  ///
    4545  /// \tparam PR Type of the priorities of the items.
    4646  /// \tparam IM A read-writable item map with \c int values, used
    4747  /// internally to handle the cross references.
    48   /// \tparam K The degree of the heap, each node have at most \e K
     48  /// \tparam D The degree of the heap, each node have at most \e D
    4949  /// children. The default is 16. Powers of two are suggested to use
    5050  /// so that the multiplications and divisions needed to traverse the
     
    5656  ///\sa FouraryHeap
    5757#ifdef DOXYGEN
    58   template <typename PR, typename IM, int K, typename CMP>
     58  template <typename PR, typename IM, int D, typename CMP>
    5959#else
    60   template <typename PR, typename IM, int K = 16,
     60  template <typename PR, typename IM, int D = 16,
    6161            typename CMP = std::less<PR> >
    6262#endif
    63   class KaryHeap {
     63  class DHeap {
    6464  public:
    6565    /// Type of the item-int map.
     
    100100    /// It is used internally to handle the cross references.
    101101    /// 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) {}
    103103
    104104    /// \brief Constructor.
     
    109109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    110110    /// \param comp The function object used for comparing the priorities.
    111     KaryHeap(ItemIntMap &map, const Compare &comp)
     111    DHeap(ItemIntMap &map, const Compare &comp)
    112112      : _iim(map), _comp(comp) {}
    113113
     
    132132
    133133  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; }
    136136
    137137    bool less(const Pair &p1, const Pair &p2) const {
     
    152152      if( length>1 ) {
    153153        int child = firstChild(hole);
    154         while( child+K<=length ) {
     154        while( child+D<=length ) {
    155155          int min=child;
    156           for (int i=1; i<K; ++i) {
     156          for (int i=1; i<D; ++i) {
    157157            if( less(_data[child+i], _data[min]) )
    158158              min=child+i;
     
    346346    }
    347347
    348   }; // class KaryHeap
     348  }; // class DHeap
    349349
    350350} // namespace lemon
    351351
    352 #endif // LEMON_KARY_HEAP_H
     352#endif // LEMON_DHEAP_H
Note: See TracChangeset for help on using the changeset viewer.