14 //! A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
15 //! The elements are sorted by integer keys.
18 static const unsigned tree_arity = 4;
20 MinIDQueue():heap_size(0){}
22 explicit MinIDQueue(unsigned id_count):
23 id_pos(id_count, invalid_id),
27 //! Returns whether the queue is empty. Equivalent to checking whether size() returns 0.
29 return heap_size == 0;
32 //! Returns the number of elements in the queue.
37 //! Returns the id_count value passed to the constructor.
38 unsigned id_count()const{
42 //! Checks whether an element is in the queue.
43 bool contains_id(unsigned id){
44 assert(id < id_count());
45 return id_pos[id] != invalid_id;
48 //! Removes all elements from the queue.
50 for(unsigned i=0; i<heap_size; ++i)
51 id_pos[heap[i].id] = invalid_id;
55 friend void swap(MinIDQueue&l, MinIDQueue&r){
57 swap(l.id_pos, r.id_pos);
60 swap(l.heap_size, r.heap_size);
63 //! Returns the current key of an element.
64 //! Undefined if the element is not part of the queue.
65 unsigned get_key(unsigned id)const{
66 assert(id < id_count());
67 assert(id_pos[id] != invalid_id);
68 return heap[id_pos[id]].key;
71 //! Returns the smallest element key pair without removing it from the queue.
72 IDKeyPair peek()const{
77 //! Returns the smallest element key pair and removes it form the queue.
81 std::swap(heap[0].key, heap[heap_size].key);
82 std::swap(heap[0].id, heap[heap_size].id);
83 id_pos[heap[0].id] = 0;
84 id_pos[heap[heap_size].id] = invalid_id;
87 return heap[heap_size];
90 //! Inserts a element key pair.
91 //! Undefined if the element is part of the queue.
92 void push(IDKeyPair p){
93 assert(p.id < id_count());
94 assert(!contains_id(p.id));
96 unsigned pos = heap_size;
100 move_up_in_tree(pos);
103 //! Updates the key of an element if the new key is smaller than the old key.
104 //! Does nothing if the new key is larger.
105 //! Undefined if the element is not part of the queue.
106 bool decrease_key(IDKeyPair p){
107 assert(p.id < id_count());
108 assert(contains_id(p.id));
110 unsigned pos = id_pos[p.id];
112 if(heap[pos].key > p.key){
113 heap[pos].key = p.key;
114 move_up_in_tree(pos);
121 //! Updates the key of an element if the new key is larger than the old key.
122 //! Does nothing if the new key is smaller.
123 //! Undefined if the element is not part of the queue.
124 bool increase_key(IDKeyPair p){
125 assert(p.id < id_count());
126 assert(contains_id(p.id));
128 unsigned pos = id_pos[p.id];
130 if(heap[pos].key < p.key){
131 heap[pos].key = p.key;
132 move_down_in_tree(pos);
140 void move_up_in_tree(unsigned pos){
142 unsigned parent = (pos-1)/tree_arity;
143 if(heap[parent].key > heap[pos].key){
144 std::swap(heap[pos], heap[parent]);
145 std::swap(id_pos[heap[pos].id], id_pos[heap[parent].id]);
151 void move_down_in_tree(unsigned pos){
153 unsigned first_child = tree_arity*pos+1;
154 if(first_child >= heap_size)
155 return; // no children
156 unsigned smallest_child = first_child;
157 for(unsigned c = first_child+1; c < std::min(tree_arity*pos+tree_arity+1, heap_size); ++c){
158 if(heap[smallest_child].key > heap[c].key){
163 if(heap[smallest_child].key >= heap[pos].key)
164 return; // no child is smaller
166 std::swap(heap[pos], heap[smallest_child]);
167 std::swap(id_pos[heap[pos].id], id_pos[heap[smallest_child].id]);
168 pos = smallest_child;
172 std::vector<unsigned>id_pos;
173 std::vector<IDKeyPair>heap;