129 |
129 |
130 bool less(const Pair &p1, const Pair &p2) const { |
130 bool less(const Pair &p1, const Pair &p2) const { |
131 return _comp(p1.second, p2.second); |
131 return _comp(p1.second, p2.second); |
132 } |
132 } |
133 |
133 |
134 int findMin(const int child, const int length) { |
|
135 int min=child; |
|
136 if( child+3<length ) { |
|
137 if( less(_data[child+3], _data[min]) ) |
|
138 min=child+3; |
|
139 if( less(_data[child+2], _data[min]) ) |
|
140 min=child+2; |
|
141 if( less(_data[child+1], _data[min]) ) |
|
142 min=child+1; |
|
143 } |
|
144 else if( child+2<length ) { |
|
145 if( less(_data[child+2], _data[min]) ) |
|
146 min=child+2; |
|
147 if( less(_data[child+1], _data[min]) ) |
|
148 min=child+1; |
|
149 } |
|
150 else if( child+1<length ) { |
|
151 if( less(_data[child+1], _data[min]) ) |
|
152 min=child+1; |
|
153 } |
|
154 return min; |
|
155 } |
|
156 |
|
157 void bubbleUp(int hole, Pair p) { |
134 void bubbleUp(int hole, Pair p) { |
158 int par = parent(hole); |
135 int par = parent(hole); |
159 while( hole>0 && less(p,_data[par]) ) { |
136 while( hole>0 && less(p,_data[par]) ) { |
160 move(_data[par],hole); |
137 move(_data[par],hole); |
161 hole = par; |
138 hole = par; |
165 } |
142 } |
166 |
143 |
167 void bubbleDown(int hole, Pair p, int length) { |
144 void bubbleDown(int hole, Pair p, int length) { |
168 if( length>1 ) { |
145 if( length>1 ) { |
169 int child = firstChild(hole); |
146 int child = firstChild(hole); |
170 while( child<length ) { |
147 while( child+3<length ) { |
171 child = findMin(child, length); |
148 int min=child; |
172 if( !less(_data[child], p) ) |
149 if( less(_data[++child], _data[min]) ) min=child; |
|
150 if( less(_data[++child], _data[min]) ) min=child; |
|
151 if( less(_data[++child], _data[min]) ) min=child; |
|
152 if( !less(_data[min], p) ) |
173 goto ok; |
153 goto ok; |
174 move(_data[child], hole); |
154 move(_data[min], hole); |
175 hole = child; |
155 hole = min; |
176 child = firstChild(hole); |
156 child = firstChild(hole); |
|
157 } |
|
158 if ( child<length ) { |
|
159 int min = child; |
|
160 if( ++child<length && less(_data[child], _data[min]) ) min=child; |
|
161 if( ++child<length && less(_data[child], _data[min]) ) min=child; |
|
162 if( less(_data[min], p) ) { |
|
163 move(_data[min], hole); |
|
164 hole = min; |
|
165 } |
177 } |
166 } |
178 } |
167 } |
179 ok: |
168 ok: |
180 move(p, hole); |
169 move(p, hole); |
181 } |
170 } |