r753:9314d9339475
Mon, 20 Jul 2009 19:06:39
[Not Reviewed]
0 comments (0 inline)
0
2
0
17
28
20
15
| ... | ... |
@@ -122,68 +122,57 @@ |
| 122 | 122 |
/// then you should set the cross reference map to \c PRE_HEAP |
| 123 | 123 |
/// for each item. |
| 124 | 124 |
void clear() { _data.clear(); }
|
| 125 | 125 |
|
| 126 | 126 |
private: |
| 127 | 127 |
static int parent(int i) { return (i-1)/4; }
|
| 128 | 128 |
static int firstChild(int i) { return 4*i+1; }
|
| 129 | 129 |
|
| 130 | 130 |
bool less(const Pair &p1, const Pair &p2) const {
|
| 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]) ) {
|
| 160 | 137 |
move(_data[par],hole); |
| 161 | 138 |
hole = par; |
| 162 | 139 |
par = parent(hole); |
| 163 | 140 |
} |
| 164 | 141 |
move(p, hole); |
| 165 | 142 |
} |
| 166 | 143 |
|
| 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); |
| 181 | 170 |
} |
| 182 | 171 |
|
| 183 | 172 |
void move(const Pair &p, int i) {
|
| 184 | 173 |
_data[i] = p; |
| 185 | 174 |
_iim.set(p.first, i); |
| 186 | 175 |
} |
| 187 | 176 |
|
| 188 | 177 |
public: |
| 189 | 178 |
/// \brief Insert a pair of item and priority into the heap. |
| ... | ... |
@@ -129,55 +129,60 @@ |
| 129 | 129 |
/// then you should set the cross reference map to \c PRE_HEAP |
| 130 | 130 |
/// for each item. |
| 131 | 131 |
void clear() { _data.clear(); }
|
| 132 | 132 |
|
| 133 | 133 |
private: |
| 134 | 134 |
int parent(int i) { return (i-1)/K; }
|
| 135 | 135 |
int firstChild(int i) { return K*i+1; }
|
| 136 | 136 |
|
| 137 | 137 |
bool less(const Pair &p1, const Pair &p2) const {
|
| 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]) ) {
|
| 154 | 144 |
move(_data[par],hole); |
| 155 | 145 |
hole = par; |
| 156 | 146 |
par = parent(hole); |
| 157 | 147 |
} |
| 158 | 148 |
move(p, hole); |
| 159 | 149 |
} |
| 160 | 150 |
|
| 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); |
| 175 | 180 |
} |
| 176 | 181 |
|
| 177 | 182 |
void move(const Pair &p, int i) {
|
| 178 | 183 |
_data[i] = p; |
| 179 | 184 |
_iim.set(p.first, i); |
| 180 | 185 |
} |
| 181 | 186 |
|
| 182 | 187 |
public: |
| 183 | 188 |
/// \brief Insert a pair of item and priority into the heap. |
0 comments (0 inline)