2 pqueue.hh -- declare PQueue_ent and PQueue
4 source file of the Flower Library
6 (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
15 template<class K, class T>
22 template<class K, class T>
23 int compare (PQueue_ent<K,T> const &e1 , PQueue_ent<K,T> const &e2) {
24 return compare (e1.key , e2.key);
28 Priority queue using a (variable size) in-situ heap.
32 TODO: add increase/decrease operations,
39 return heap_array_[i-1];
41 T const&elt (int i) const {
42 return heap_array_[i-1];
45 /** acces an heap element. Careful with this, as changing the
46 priority might fuck up the invariants
48 @param 1 <= i < size () */
49 T& operator[] (int i) { return heap_array_[i]; }
50 T operator[] (int i) const { return heap_array_[i]; }
54 for (int i =2; i <= size (); i++)
55 assert (compare (elt (i/2), elt (i)) <= 0);
58 T front () const { return elt (1); }
59 int size () const { return heap_array_.size (); }
62 int i = heap_array_.size ();
65 if (compare (elt (j), v) > 0) {
77 //int first_leaf_i = size ();
83 T last = heap_array_.top ();
88 while (mini < size ()) {
89 if (compare (elt (mini + 1), elt (mini)) <0)
91 if (compare (last,elt (mini)) < 0)
93 elt (lasti) = elt (mini);