lemon/pairing_heap.h
changeset 745 68792fb2870f
parent 703 bb3392fe91f2
equal deleted inserted replaced
2:ffc39e0e1e94 3:04dc91422b0a
   206     /// \brief Remove the item having minimum priority.
   206     /// \brief Remove the item having minimum priority.
   207     ///
   207     ///
   208     /// This function removes the item having minimum priority.
   208     /// This function removes the item having minimum priority.
   209     /// \pre The heap must be non-empty.
   209     /// \pre The heap must be non-empty.
   210     void pop() {
   210     void pop() {
   211       int TreeArray[_num_items];
   211       std::vector<int> trees;
   212       int i=0, num_child=0, child_right = 0;
   212       int i=0, child_right = 0;
   213       _data[_min].in=false;
   213       _data[_min].in=false;
   214 
   214 
   215       if( -1!=_data[_min].child ) {
   215       if( -1!=_data[_min].child ) {
   216         i=_data[_min].child;
   216         i=_data[_min].child;
   217         TreeArray[num_child] = i;
   217         trees.push_back(i);
   218         _data[i].parent = -1;
   218         _data[i].parent = -1;
   219         _data[_min].child = -1;
   219         _data[_min].child = -1;
   220 
   220 
   221         ++num_child;
       
   222         int ch=-1;
   221         int ch=-1;
   223         while( _data[i].child!=-1 ) {
   222         while( _data[i].child!=-1 ) {
   224           ch=_data[i].child;
   223           ch=_data[i].child;
   225           if( _data[ch].left_child && i==_data[ch].parent ) {
   224           if( _data[ch].left_child && i==_data[ch].parent ) {
   226             i=ch;
   225             break;
   227             //break;
       
   228           } else {
   226           } else {
   229             if( _data[ch].left_child ) {
   227             if( _data[ch].left_child ) {
   230               child_right=_data[ch].parent;
   228               child_right=_data[ch].parent;
   231               _data[ch].parent = i;
   229               _data[ch].parent = i;
   232               --_data[i].degree;
   230               --_data[i].degree;
   235               child_right=ch;
   233               child_right=ch;
   236               _data[i].child=-1;
   234               _data[i].child=-1;
   237               _data[i].degree=0;
   235               _data[i].degree=0;
   238             }
   236             }
   239             _data[child_right].parent = -1;
   237             _data[child_right].parent = -1;
   240             TreeArray[num_child] = child_right;
   238             trees.push_back(child_right);
   241             i = child_right;
   239             i = child_right;
   242             ++num_child;
   240           }
   243           }
   241         }
   244         }
   242 
   245 
   243         int num_child = trees.size();
   246         int other;
   244         int other;
   247         for( i=0; i<num_child-1; i+=2 ) {
   245         for( i=0; i<num_child-1; i+=2 ) {
   248           if ( !_comp(_data[TreeArray[i]].prio,
   246           if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
   249                      _data[TreeArray[i+1]].prio) ) {
   247             other=trees[i];
   250             other=TreeArray[i];
   248             trees[i]=trees[i+1];
   251             TreeArray[i]=TreeArray[i+1];
   249             trees[i+1]=other;
   252             TreeArray[i+1]=other;
   250           }
   253           }
   251           fuse( trees[i], trees[i+1] );
   254           fuse( TreeArray[i], TreeArray[i+1] );
       
   255         }
   252         }
   256 
   253 
   257         i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
   254         i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
   258         while(i>=2) {
   255         while(i>=2) {
   259           if ( _comp(_data[TreeArray[i]].prio,
   256           if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
   260                     _data[TreeArray[i-2]].prio) ) {
   257             other=trees[i];
   261             other=TreeArray[i];
   258             trees[i]=trees[i-2];
   262             TreeArray[i]=TreeArray[i-2];
   259             trees[i-2]=other;
   263             TreeArray[i-2]=other;
   260           }
   264           }
   261           fuse( trees[i-2], trees[i] );
   265           fuse( TreeArray[i-2], TreeArray[i] );
       
   266           i-=2;
   262           i-=2;
   267         }
   263         }
   268         _min = TreeArray[0];
   264         _min = trees[0];
   269       }
   265       }
   270 
   266       else {
   271       if ( 0==num_child ) {
       
   272         _min = _data[_min].child;
   267         _min = _data[_min].child;
   273       }
   268       }
   274 
   269 
   275       if (_min >= 0) _data[_min].left_child = false;
   270       if (_min >= 0) _data[_min].left_child = false;
   276 
       
   277       --_num_items;
   271       --_num_items;
   278     }
   272     }
   279 
   273 
   280     /// \brief Remove the given item from the heap.
   274     /// \brief Remove the given item from the heap.
   281     ///
   275     ///