2 pqueue.hh -- declare PQueue_ent and PQueue
4 source file of the Flower Library
6 (c) 1997--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
11 #include "std-vector.hh"
13 template<class K, class T>
20 template<class K, class T>
21 int compare (PQueue_ent<K, T> const &e1, PQueue_ent<K, T> const &e2)
23 return compare (e1.key, e2.key);
27 Priority queue using a (variable size) in-situ heap.
31 TODO: add increase/decrease operations,
37 vector<T> heap_array_;
40 return heap_array_[i - 1];
42 T const &elt (vsize i) const
44 return heap_array_[i - 1];
47 /** acces an heap element. Careful with this, as changing the
48 priority might fuck up the invariants
50 @param 1 <= i < size () */
51 T &operator [] (vsize i)
53 return heap_array_[i];
55 T operator [] (vsize i) const
57 return heap_array_[i];
62 for (vsize i = 2; i <= size (); i++)
63 assert (compare (elt (i / 2), elt (i)) <= 0);
72 return heap_array_.size ();
76 heap_array_.push_back (v);
77 vsize i = heap_array_.size ();
81 if (compare (elt (j), v) > 0)
95 //int first_leaf_i = size ();
102 T last = heap_array_.back ();
107 while (mini < size ())
109 if (compare (elt (mini + 1), elt (mini)) < 0)
111 if (compare (last, elt (mini)) < 0)
113 elt (lasti) = elt (mini);
118 heap_array_.pop_back ();