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