LEMON/LEMON-main Changeset - r706:9314d9339475

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r706:9314d9339475

« 705:39a5b4

707:3887d6 »

r706:9314d9339475

Mon, 20 Jul 2009 19:06:39

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Smarter bubbleDown() in K-ary heaps (#301)

0 2 0

default

2 files changed with 37 insertions and 43 deletions:

lemon/fourary_heap.h

lemon/kary_heap.h

↑ Collapse diff ↑

lemon/fourary_heap.h

Show inline comments

@@ -86,140 +86,129 @@
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    FouraryHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() { _data.clear(); }
 		  private:
 		    static int parent(int i) { return (i-1)/4; }
 		    static int firstChild(int i) { return 4*i+1; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    int findMin(const int child, const int length) {
 		      int min=child;
 		      if( child+3<length ) {
 		        if( less(_data[child+3], _data[min]) )
 		          min=child+3;
 		        if( less(_data[child+2], _data[min]) )
 		          min=child+2;
 		        if( less(_data[child+1], _data[min]) )
 		          min=child+1;
+		      }
 		      else if( child+2<length ) {
 		        if( less(_data[child+2], _data[min]) )
 		          min=child+2;
 		        if( less(_data[child+1], _data[min]) )
 		          min=child+1;
+		      }
 		      else if( child+1<length ) {
 		        if( less(_data[child+1], _data[min]) )
 		          min=child+1;
+		      }
 		      return min;
+		    }
 		    void bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
+		    }
 		    void bubbleDown(int hole, Pair p, int length) {
 		      if( length>1 ) {
 		        int child = firstChild(hole);
 		        while( child<length ) {
 		          child = findMin(child, length);
-		          if( !less(_data[child], p) )
+		        while( child+3<length ) {
 		          int min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( !less(_data[min], p) )
 		            goto ok;
 		          move(_data[child], hole);
 		          hole = child;
 		          move(_data[min], hole);
 		          hole = min;
 		          child = firstChild(hole);
+		        }
 		        if ( child<length ) {
 		          int min = child;
 		          if( ++child<length && less(_data[child], _data[min]) ) min=child;
 		          if( ++child<length && less(_data[child], _data[min]) ) min=child;
 		          if( less(_data[min], p) ) {
 		            move(_data[min], hole);
 		            hole = min;
+		          }
+		        }
+		      }
 		    ok:
 		      move(p, hole);
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair &p) {
 		      int n = _data.size();
 		      _data.resize(n+1);
 		      bubbleUp(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[0].first; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[0].second; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.

lemon/kary_heap.h

Show inline comments

@@ -93,127 +93,132 @@
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// 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) {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// 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)
 		      : _iim(map), _comp(comp) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() { _data.clear(); }
 		  private:
 		    int parent(int i) { return (i-1)/K; }
 		    int firstChild(int i) { return K*i+1; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    int findMin(const int child, const int length) {
 		      int min=child, i=1;
 		      while( i<K && child+i<length ) {
 		        if( less(_data[child+i], _data[min]) )
 		          min=child+i;
 		        ++i;
+		      }
 		      return min;
+		    }
 		    void bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
+		    }
 		    void bubbleDown(int hole, Pair p, int length) {
 		      if( length>1 ) {
 		        int child = firstChild(hole);
 		        while( child<length ) {
 		          child = findMin(child, length);
-		          if( !less(_data[child], p) )
+		        while( child+K<=length ) {
 		          int min=child;
 		          for (int i=1; i<K; ++i) {
 		            if( less(_data[child+i], _data[min]) )
 		              min=child+i;
+		          }
 		          if( !less(_data[min], p) )
 		            goto ok;
 		          move(_data[child], hole);
 		          hole = child;
 		          move(_data[min], hole);
 		          hole = min;
 		          child = firstChild(hole);
+		        }
 		        if ( child<length ) {
 		          int min = child;
 		          while (++child < length) {
 		            if( less(_data[child], _data[min]) )
 		              min=child;
+		          }
 		          if( less(_data[min], p) ) {
 		            move(_data[min], hole);
 		            hole = min;
+		          }
+		        }
+		      }
 		    ok:
 		      move(p, hole);
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// This function inserts \c p.first to the heap with priority
 		    /// \c p.second.
 		    /// \param p The pair to insert.
 		    /// \pre \c p.first must not be stored in the heap.
 		    void push(const Pair &p) {
 		      int n = _data.size();
 		      _data.resize(n+1);
 		      bubbleUp(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    /// \pre \e i must not be stored in the heap.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[0].first; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[0].second; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.

0 comments (0 inline)

RhodeCode

Login to your account