gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small improvements in heap implementations (#301)
0 2 0
default
2 files changed with 28 insertions and 32 deletions:
↑ Collapse diff ↑
Ignore white space 24 line context
... ...
@@ -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.
Ignore white space 6 line context
... ...
@@ -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
        TreeArray[num_child] = i;
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
            TreeArray[num_child] = child_right;
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
            TreeArray[i+1]=other;
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( TreeArray[i], TreeArray[i+1] );
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
            TreeArray[i-2]=other;
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( TreeArray[i-2], TreeArray[i] );
261
          fuse( trees[i-2], trees[i] );
266 262
          i-=2;
267 263
        }
268
        _min = TreeArray[0];
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)