lemon/bucket_heap.h
changeset 808 9c428bb2b105
parent 710 f1fe0ddad6f7
child 877 141f9c0db4a3
equal deleted inserted replaced
4:b308b274dada 5:59eb03ace26a
   140       _data.clear(); _first.clear(); _minimum = 0;
   140       _data.clear(); _first.clear(); _minimum = 0;
   141     }
   141     }
   142 
   142 
   143   private:
   143   private:
   144 
   144 
   145     void relocate_last(int idx) {
   145     void relocateLast(int idx) {
   146       if (idx + 1 < int(_data.size())) {
   146       if (idx + 1 < int(_data.size())) {
   147         _data[idx] = _data.back();
   147         _data[idx] = _data.back();
   148         if (_data[idx].prev != -1) {
   148         if (_data[idx].prev != -1) {
   149           _data[_data[idx].prev].next = idx;
   149           _data[_data[idx].prev].next = idx;
   150         } else {
   150         } else {
   241         Direction::increase(_minimum);
   241         Direction::increase(_minimum);
   242       }
   242       }
   243       int idx = _first[_minimum];
   243       int idx = _first[_minimum];
   244       _iim[_data[idx].item] = -2;
   244       _iim[_data[idx].item] = -2;
   245       unlace(idx);
   245       unlace(idx);
   246       relocate_last(idx);
   246       relocateLast(idx);
   247     }
   247     }
   248 
   248 
   249     /// \brief Remove the given item from the heap.
   249     /// \brief Remove the given item from the heap.
   250     ///
   250     ///
   251     /// This function removes the given item from the heap if it is
   251     /// This function removes the given item from the heap if it is
   254     /// \pre \e i must be in the heap.
   254     /// \pre \e i must be in the heap.
   255     void erase(const Item &i) {
   255     void erase(const Item &i) {
   256       int idx = _iim[i];
   256       int idx = _iim[i];
   257       _iim[_data[idx].item] = -2;
   257       _iim[_data[idx].item] = -2;
   258       unlace(idx);
   258       unlace(idx);
   259       relocate_last(idx);
   259       relocateLast(idx);
   260     }
   260     }
   261 
   261 
   262     /// \brief The priority of the given item.
   262     /// \brief The priority of the given item.
   263     ///
   263     ///
   264     /// This function returns the priority of the given item.
   264     /// This function returns the priority of the given item.