r706:9314d9339475
Mon, 20 Jul 2009 19:06:39
[Not Reviewed]
0 comments (0 inline)
0
2
0
17
28
20
15
| ... | ... |
@@ -131,29 +131,6 @@ |
| 131 | 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 | 134 |
void bubbleUp(int hole, Pair p) {
|
| 158 | 135 |
int par = parent(hole); |
| 159 | 136 |
while( hole>0 && less(p,_data[par]) ) {
|
| ... | ... |
@@ -167,14 +144,26 @@ |
| 167 | 144 |
void bubbleDown(int hole, Pair p, int length) {
|
| 168 | 145 |
if( length>1 ) {
|
| 169 | 146 |
int child = firstChild(hole); |
| 170 |
while( child<length ) {
|
|
| 171 |
child = findMin(child, length); |
|
| 172 |
|
|
| 147 |
while( child+3<length ) {
|
|
| 148 |
int min=child; |
|
| 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 | 153 |
goto ok; |
| 174 |
move(_data[child], hole); |
|
| 175 |
hole = child; |
|
| 154 |
move(_data[min], hole); |
|
| 155 |
hole = min; |
|
| 176 | 156 |
child = firstChild(hole); |
| 177 | 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 |
} |
|
| 166 |
} |
|
| 178 | 167 |
} |
| 179 | 168 |
ok: |
| 180 | 169 |
move(p, hole); |
| ... | ... |
@@ -138,16 +138,6 @@ |
| 138 | 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 | 141 |
void bubbleUp(int hole, Pair p) {
|
| 152 | 142 |
int par = parent(hole); |
| 153 | 143 |
while( hole>0 && less(p,_data[par]) ) {
|
| ... | ... |
@@ -161,14 +151,29 @@ |
| 161 | 151 |
void bubbleDown(int hole, Pair p, int length) {
|
| 162 | 152 |
if( length>1 ) {
|
| 163 | 153 |
int child = firstChild(hole); |
| 164 |
while( child<length ) {
|
|
| 165 |
child = findMin(child, length); |
|
| 166 |
|
|
| 154 |
while( child+K<=length ) {
|
|
| 155 |
int min=child; |
|
| 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 | 161 |
goto ok; |
| 168 |
move(_data[child], hole); |
|
| 169 |
hole = child; |
|
| 162 |
move(_data[min], hole); |
|
| 163 |
hole = min; |
|
| 170 | 164 |
child = firstChild(hole); |
| 171 | 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 |
} |
|
| 176 |
} |
|
| 172 | 177 |
} |
| 173 | 178 |
ok: |
| 174 | 179 |
move(p, hole); |
0 comments (0 inline)