13 * |
13 * |
14 *int size() : returns the number of elements in the heap |
14 *int size() : returns the number of elements in the heap |
15 * |
15 * |
16 *bool empty() : true iff size()=0 |
16 *bool empty() : true iff size()=0 |
17 * |
17 * |
18 *void push(Item, Prio) : pushes Item to the heap with priority Prio. If |
18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not |
19 * Item was already in the heap, it calls decrease(Item, Prio) |
19 * in the heap, and calls decrease/increase(Item, Prio) otherwise |
|
20 * |
|
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item |
|
22 * mustn't be in the heap. |
20 * |
23 * |
21 *Item top() : returns the Item with least Prio |
24 *Item top() : returns the Item with least Prio |
22 * |
25 * |
23 *Prio prio() : returns the least Prio |
26 *Prio prio() : returns the least Prio |
24 * |
27 * |
26 * |
29 * |
27 *void pop() : deletes the Item with least Prio |
30 *void pop() : deletes the Item with least Prio |
28 * |
31 * |
29 *void erase(Item) : deletes Item from the heap if it was already there |
32 *void erase(Item) : deletes Item from the heap if it was already there |
30 * |
33 * |
31 *void decrease(Item, P) : If Item was not in the heap, then it calls |
34 *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap |
32 * push(Item, P). If item is in the heap with Prio more than P |
35 * with prio at least P. |
33 * then sets its Prio to P. |
36 * |
34 * |
37 *void increase(Item, P) : sets prio of Item to P. |
35 *void increase(Item, P) : If Item was not in the heap, then it calls |
|
36 * push(Item, P). If item is in the heap with Prio less than P |
|
37 * then sets its Prio to P. |
|
38 * |
38 * |
39 * |
39 * |
40 *In Fibonacci heaps, increase and erase are not efficient, in case of |
40 *In Fibonacci heaps, increase and erase are not efficient, in case of |
41 *many calls to these operations, it is better to use bin_heap. |
41 *many calls to these operations, it is better to use bin_heap. |
42 */ |
42 */ |
78 if ( container[i].in ) ++s; |
78 if ( container[i].in ) ++s; |
79 return s; |
79 return s; |
80 } |
80 } |
81 |
81 |
82 |
82 |
83 bool empty() const { return blank; } |
83 bool empty() const { return blank; } |
84 |
84 |
85 |
85 |
86 void push (Item const it, PrioType const value) |
86 void set (Item const it, PrioType const value) { |
87 { |
87 int i=iimap.get(it); |
88 |
88 if ( i >= 0 && container[i].in ) { |
89 int i=iimap.get(it); |
89 if ( !comp(container[i].prio, value) ) decrease(it, value); |
90 |
90 if ( comp(container[i].prio, value) ) increase(it, value); |
91 if ( i >= 0 && container[i].in ) decrease(it, value); |
91 } else push(it, value); |
92 else { |
92 } |
93 if ( i < 0 ) { |
93 |
94 int s=container.size(); |
94 |
95 iimap.set( it, s ); |
95 void push (Item const it, PrioType const value) { |
96 store st; |
96 int i=iimap.get(it); |
97 st.name=it; |
97 if ( i < 0 ) { |
98 container.push_back(st); |
98 int s=container.size(); |
99 i=s; |
99 iimap.set( it, s ); |
100 } |
100 store st; |
101 |
101 st.name=it; |
102 if ( !blank ) { |
102 container.push_back(st); |
103 container[container[minimum].right_neighbor].left_neighbor=i; |
103 i=s; |
104 container[i].right_neighbor=container[minimum].right_neighbor; |
104 } |
105 container[minimum].right_neighbor=i; |
105 |
106 container[i].left_neighbor=minimum; |
106 if ( !blank ) { |
107 if ( !comp( container[minimum].prio, value) ) minimum=i; |
107 container[container[minimum].right_neighbor].left_neighbor=i; |
108 |
108 container[i].right_neighbor=container[minimum].right_neighbor; |
109 |
109 container[minimum].right_neighbor=i; |
110 |
110 container[i].left_neighbor=minimum; |
111 } else { |
111 if ( !comp( container[minimum].prio, value) ) minimum=i; |
112 container[i].right_neighbor=container[i].left_neighbor=i; |
112 |
113 minimum=i; |
113 } else { |
114 blank=false; |
114 container[i].right_neighbor=container[i].left_neighbor=i; |
115 } |
115 minimum=i; |
116 container[i].prio=value; |
116 blank=false; |
117 } |
117 } |
118 } |
118 container[i].prio=value; |
|
119 } |
|
120 |
119 |
121 |
120 |
122 |
121 Item top() const { |
123 Item top() const { |
122 if ( !blank ) { |
124 if ( !blank ) { |
123 return container[minimum].name; |
125 return container[minimum].name; |
197 pop(); |
199 pop(); |
198 } |
200 } |
199 } |
201 } |
200 |
202 |
201 |
203 |
202 void decrease (Item it, PrioType const value) { |
204 void decrease (Item it, PrioType const value) { |
203 int i=iimap.get(it); |
205 int i=iimap.get(it); |
204 if ( i >= 0 && container[i].in ) { |
206 container[i].prio=value; |
205 |
207 int p=container[i].parent; |
206 if ( comp(value, container[i].prio) ) { |
208 |
207 container[i].prio=value; |
209 if ( p!=-1 && comp(value, container[p].prio) ) { |
208 |
210 cut(i,p); |
209 if ( container[i].parent!=-1 ) { |
211 cascade(p); |
210 int p=container[i].parent; |
212 if ( comp(value, container[minimum].prio) ) minimum=i; |
211 |
213 } |
212 if ( !comp(container[p].prio, value) ) { |
214 } |
213 cut(i,p); |
|
214 cascade(p); |
|
215 if ( comp(value, container[minimum].prio) ) minimum=i; |
|
216 } |
|
217 } |
|
218 } |
|
219 } else push(it, value); |
|
220 } |
|
221 |
215 |
222 |
216 |
223 void increase (Item it, PrioType const value) { |
217 void increase (Item it, PrioType const value) { |
224 int i=iimap.get(it); |
218 erase(it); |
225 |
219 push(it, value); |
226 if ( i >= 0 && container[i].in ) { |
|
227 if ( comp(container[i].prio, value) ) { |
|
228 erase(it); |
|
229 push(it, value); |
|
230 } |
|
231 } else push(it, value); |
|
232 } |
220 } |
233 |
221 |
234 |
222 |
235 private: |
223 private: |
236 |
224 |