r752:39a5b48bcace
Fri, 10 Jul 2009 09:17:13
[Not Reviewed]
0 comments (0 inline)
0
2
0
18
24
| ... | ... |
@@ -156,32 +156,34 @@ |
| 156 | 156 |
|
| 157 | 157 |
void bubbleUp(int hole, Pair p) {
|
| 158 | 158 |
int par = parent(hole); |
| 159 | 159 |
while( hole>0 && less(p,_data[par]) ) {
|
| 160 | 160 |
move(_data[par],hole); |
| 161 | 161 |
hole = par; |
| 162 | 162 |
par = parent(hole); |
| 163 | 163 |
} |
| 164 | 164 |
move(p, hole); |
| 165 | 165 |
} |
| 166 | 166 |
|
| 167 | 167 |
void bubbleDown(int hole, Pair p, int length) {
|
| 168 |
int child = firstChild(hole); |
|
| 169 |
while( child<length && length>1 ) {
|
|
| 170 |
child = findMin(child,length); |
|
| 171 |
if( !less(_data[child], p) ) |
|
| 172 |
goto ok; |
|
| 173 |
move(_data[child], hole); |
|
| 174 |
hole = child; |
|
| 175 |
child = firstChild(hole); |
|
| 168 |
if( length>1 ) {
|
|
| 169 |
int child = firstChild(hole); |
|
| 170 |
while( child<length ) {
|
|
| 171 |
child = findMin(child, length); |
|
| 172 |
if( !less(_data[child], p) ) |
|
| 173 |
goto ok; |
|
| 174 |
move(_data[child], hole); |
|
| 175 |
hole = child; |
|
| 176 |
child = firstChild(hole); |
|
| 177 |
} |
|
| 176 | 178 |
} |
| 177 | 179 |
ok: |
| 178 | 180 |
move(p, hole); |
| 179 | 181 |
} |
| 180 | 182 |
|
| 181 | 183 |
void move(const Pair &p, int i) {
|
| 182 | 184 |
_data[i] = p; |
| 183 | 185 |
_iim.set(p.first, i); |
| 184 | 186 |
} |
| 185 | 187 |
|
| 186 | 188 |
public: |
| 187 | 189 |
/// \brief Insert a pair of item and priority into the heap. |
| ... | ... |
@@ -199,90 +199,84 @@ |
| 199 | 199 |
/// This function returns the priority of the given item. |
| 200 | 200 |
/// \param item The item. |
| 201 | 201 |
/// \pre \e item must be in the heap. |
| 202 | 202 |
const Prio& operator[](const Item& item) const {
|
| 203 | 203 |
return _data[_iim[item]].prio; |
| 204 | 204 |
} |
| 205 | 205 |
|
| 206 | 206 |
/// \brief Remove the item having minimum priority. |
| 207 | 207 |
/// |
| 208 | 208 |
/// This function removes the item having minimum priority. |
| 209 | 209 |
/// \pre The heap must be non-empty. |
| 210 | 210 |
void pop() {
|
| 211 |
int TreeArray[_num_items]; |
|
| 212 |
int i=0, num_child=0, child_right = 0; |
|
| 211 |
std::vector<int> trees; |
|
| 212 |
int i=0, child_right = 0; |
|
| 213 | 213 |
_data[_min].in=false; |
| 214 | 214 |
|
| 215 | 215 |
if( -1!=_data[_min].child ) {
|
| 216 | 216 |
i=_data[_min].child; |
| 217 |
|
|
| 217 |
trees.push_back(i); |
|
| 218 | 218 |
_data[i].parent = -1; |
| 219 | 219 |
_data[_min].child = -1; |
| 220 | 220 |
|
| 221 |
++num_child; |
|
| 222 | 221 |
int ch=-1; |
| 223 | 222 |
while( _data[i].child!=-1 ) {
|
| 224 | 223 |
ch=_data[i].child; |
| 225 | 224 |
if( _data[ch].left_child && i==_data[ch].parent ) {
|
| 226 |
i=ch; |
|
| 227 |
//break; |
|
| 225 |
break; |
|
| 228 | 226 |
} else {
|
| 229 | 227 |
if( _data[ch].left_child ) {
|
| 230 | 228 |
child_right=_data[ch].parent; |
| 231 | 229 |
_data[ch].parent = i; |
| 232 | 230 |
--_data[i].degree; |
| 233 | 231 |
} |
| 234 | 232 |
else {
|
| 235 | 233 |
child_right=ch; |
| 236 | 234 |
_data[i].child=-1; |
| 237 | 235 |
_data[i].degree=0; |
| 238 | 236 |
} |
| 239 | 237 |
_data[child_right].parent = -1; |
| 240 |
|
|
| 238 |
trees.push_back(child_right); |
|
| 241 | 239 |
i = child_right; |
| 242 |
++num_child; |
|
| 243 | 240 |
} |
| 244 | 241 |
} |
| 245 | 242 |
|
| 243 |
int num_child = trees.size(); |
|
| 246 | 244 |
int other; |
| 247 | 245 |
for( i=0; i<num_child-1; i+=2 ) {
|
| 248 |
if ( !_comp(_data[TreeArray[i]].prio, |
|
| 249 |
_data[TreeArray[i+1]].prio) ) {
|
|
| 250 |
other=TreeArray[i]; |
|
| 251 |
TreeArray[i]=TreeArray[i+1]; |
|
| 252 |
|
|
| 246 |
if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
|
|
| 247 |
other=trees[i]; |
|
| 248 |
trees[i]=trees[i+1]; |
|
| 249 |
trees[i+1]=other; |
|
| 253 | 250 |
} |
| 254 |
fuse( |
|
| 251 |
fuse( trees[i], trees[i+1] ); |
|
| 255 | 252 |
} |
| 256 | 253 |
|
| 257 | 254 |
i = (0==(num_child % 2)) ? num_child-2 : num_child-1; |
| 258 | 255 |
while(i>=2) {
|
| 259 |
if ( _comp(_data[TreeArray[i]].prio, |
|
| 260 |
_data[TreeArray[i-2]].prio) ) {
|
|
| 261 |
other=TreeArray[i]; |
|
| 262 |
TreeArray[i]=TreeArray[i-2]; |
|
| 263 |
|
|
| 256 |
if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
|
|
| 257 |
other=trees[i]; |
|
| 258 |
trees[i]=trees[i-2]; |
|
| 259 |
trees[i-2]=other; |
|
| 264 | 260 |
} |
| 265 |
fuse( |
|
| 261 |
fuse( trees[i-2], trees[i] ); |
|
| 266 | 262 |
i-=2; |
| 267 | 263 |
} |
| 268 |
_min = |
|
| 264 |
_min = trees[0]; |
|
| 269 | 265 |
} |
| 270 |
|
|
| 271 |
if ( 0==num_child ) {
|
|
| 266 |
else {
|
|
| 272 | 267 |
_min = _data[_min].child; |
| 273 | 268 |
} |
| 274 | 269 |
|
| 275 | 270 |
if (_min >= 0) _data[_min].left_child = false; |
| 276 |
|
|
| 277 | 271 |
--_num_items; |
| 278 | 272 |
} |
| 279 | 273 |
|
| 280 | 274 |
/// \brief Remove the given item from the heap. |
| 281 | 275 |
/// |
| 282 | 276 |
/// This function removes the given item from the heap if it is |
| 283 | 277 |
/// already stored. |
| 284 | 278 |
/// \param item The item to delete. |
| 285 | 279 |
/// \pre \e item must be in the heap. |
| 286 | 280 |
void erase (const Item& item) {
|
| 287 | 281 |
int i=_iim[item]; |
| 288 | 282 |
if ( i>=0 && _data[i].in ) {
|
0 comments (0 inline)