/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

     /// \pre \e item must be stored in the heap with priority at least \e value.

     /// \pre \e item must be stored in the heap with priority at least \e value.

     void decrease (Item item, const Prio& value) {

     void decrease (Item item, const Prio& value) {

       int i=_iim[item];

       int i=_iim[item];

       int p=_data[i].parent;

       int p=_data[i].parent;

       _data[i].prio=value;

       _data[i].prio=value;

       while( p!=-1 && _comp(value, _data[p].prio) ) {

       while( p!=-1 && _comp(value, _data[p].prio) ) {

         _data[i].name=_data[p].name;

         _data[i].name=_data[p].name;

         _data[i].prio=_data[p].prio;

         _data[i].prio=_data[p].prio;

         _data[p].name=item;

         _data[p].name=item;

         _data[p].prio=value;

         _data[p].prio=value;

         break;

         break;

       }

       }

     }

     }

   private:

   private:

     // Find the minimum of the roots

     // Find the minimum of the roots

     int findMin() {

     int findMin() {

       if( _head!=-1 ) {

       if( _head!=-1 ) {

         int min_loc=_head, min_val=_data[_head].prio;

         int min_loc=_head, min_val=_data[_head].prio;

         for( int x=_data[_head].right_neighbor; x!=-1;

         for( int x=_data[_head].right_neighbor; x!=-1;

         _head=a;

         _head=a;

       } else {

       } else {

         interleave(a);

         interleave(a);

       }

       }

       if( _data[_head].right_neighbor==-1 ) return;

       if( _data[_head].right_neighbor==-1 ) return;

       int x=_head;

       int x=_head;

       int x_prev=-1, x_next=_data[x].right_neighbor;

       int x_prev=-1, x_next=_data[x].right_neighbor;

       while( x_next!=-1 ) {

       while( x_next!=-1 ) {

         if( _data[x].degree!=_data[x_next].degree ||

         if( _data[x].degree!=_data[x_next].degree ||

             ( _data[x_next].right_neighbor!=-1 &&

             ( _data[x_next].right_neighbor!=-1 &&

     // Interleave the elements of the given list into the list of the roots

     // Interleave the elements of the given list into the list of the roots

     void interleave(int a) {

     void interleave(int a) {

       int p=_head, q=a;

       int p=_head, q=a;

       int curr=_data.size();

       int curr=_data.size();

       _data.push_back(Store());

       _data.push_back(Store());

       while( p!=-1 || q!=-1 ) {

       while( p!=-1 || q!=-1 ) {

         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {

         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {

           _data[curr].right_neighbor=p;

           _data[curr].right_neighbor=p;

           curr=p;

           curr=p;

           p=_data[p].right_neighbor;

           p=_data[p].right_neighbor;

           _data[curr].right_neighbor=q;

           _data[curr].right_neighbor=q;

           curr=q;

           curr=q;

           q=_data[q].right_neighbor;

           q=_data[q].right_neighbor;

         }

         }

       }

       }

       _head=_data.back().right_neighbor;

       _head=_data.back().right_neighbor;

       _data.pop_back();

       _data.pop_back();

     }

     }

     // Lace node a under node b

     // Lace node a under node b