source file of the Flower Library
- (c) 1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+ (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
*/
Hungarian postfix pq
TODO: add increase/decrease operations,
- add max() operation
+ add max () operation
*/
template<class T>
class PQueue {
- Array<T> heap_arr_;
+ Array<T> heap_array_;
T &elt (int i) {
- return heap_arr_[i-1];
+ return heap_array_[i-1];
}
T const&elt (int i) const {
- return heap_arr_[i-1];
+ return heap_array_[i-1];
}
public:
/** acces an heap element. Careful with this, as changing the
priority might fuck up the invariants
- @param 1 <= i < size() */
- T& operator[](int i) { return heap_arr_[i]; }
- T operator[](int i) const { return heap_arr_[i]; }
- void OK() const
+ @param 1 <= i < size () */
+ T& operator[] (int i) { return heap_array_[i]; }
+ T operator[] (int i) const { return heap_array_[i]; }
+ void OK () const
{
#ifndef NDEBUG
- for (int i =2; i <= size(); i++)
+ for (int i =2; i <= size (); i++)
assert (compare (elt (i/2), elt (i)) <= 0);
#endif
}
- T front() const { return elt (1); }
- int size() const { return heap_arr_.size (); }
+ T front () const { return elt (1); }
+ int size () const { return heap_array_.size (); }
void insert (T v) {
- heap_arr_.push (v);
- int i = heap_arr_.size();
+ heap_array_.push (v);
+ int i = heap_array_.size ();
int j = i / 2 ;
while (j) {
if (compare (elt (j), v) > 0) {
}
}
elt (i) = v;
- OK();
+ OK ();
}
- T max() const {
- //int first_leaf_i = size();
+ T max () const {
+ //int first_leaf_i = size ();
T max_t;
return max_t;
}
- void delmin() {
- assert (size());
- T last = heap_arr_.top();
+ void delmin () {
+ assert (size ());
+ T last = heap_array_.top ();
int mini=2;
int lasti=1;
- while (mini < size()) {
+ while (mini < size ()) {
if (compare (elt (mini + 1), elt (mini)) <0)
mini++;
if (compare (last,elt (mini)) < 0)
mini *= 2;
}
elt (lasti) = last;
- heap_arr_.pop();
- OK();
+ heap_array_.pop ();
+ OK ();
}
- T get() {
- T t = front();
- delmin();
+ T get () {
+ T t = front ();
+ delmin ();
return t;
}
};