lemon/fib_heap.h
author jacint
Thu, 30 Mar 2006 15:34:56 +0000
changeset 2024 4ab8a25def3c
parent 1906 7fa90b66ca9e
child 2050 d9a221218ea4
permissions -rw-r--r--
tolerance class incorporated
alpar@906
     1
/* -*- C++ -*-
alpar@906
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906
     8
 *
alpar@906
     9
 * Permission to use, modify and distribute this software is granted
alpar@906
    10
 * provided that this copyright notice appears in all copies. For
alpar@906
    11
 * precise terms see the accompanying LICENSE file.
alpar@906
    12
 *
alpar@906
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    14
 * express or implied, and with no claim as to its suitability for any
alpar@906
    15
 * purpose.
alpar@906
    16
 *
alpar@906
    17
 */
alpar@255
    18
alpar@921
    19
#ifndef LEMON_FIB_HEAP_H
alpar@921
    20
#define LEMON_FIB_HEAP_H
alpar@255
    21
jacint@857
    22
///\file
klao@491
    23
///\ingroup auxdat
alpar@255
    24
///\brief Fibonacci Heap implementation.
alpar@255
    25
alpar@255
    26
#include <vector>
alpar@255
    27
#include <functional>
deba@1332
    28
#include <cmath>
alpar@255
    29
alpar@921
    30
namespace lemon {
alpar@255
    31
  
deba@1834
    32
  /// \ingroup auxdat
alpar@430
    33
jacint@857
    34
  /// Fibonacci Heap.
jacint@373
    35
jacint@857
    36
  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
jacint@857
    37
  ///is a data structure for storing items with specified values called \e
jacint@857
    38
  ///priorities in such a way that finding the item with minimum priority is
alpar@911
    39
  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
jacint@857
    40
  ///one can change the priority of an item, add or erase an item, etc.
jacint@857
    41
  ///
jacint@857
    42
  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
jacint@857
    43
  ///heap. In case of many calls to these operations, it is better to use a
jacint@857
    44
  ///\e binary \e heap.
jacint@857
    45
  ///
jacint@857
    46
  ///\param Item Type of the items to be stored.  
jacint@857
    47
  ///\param Prio Type of the priority of the items.
alpar@1204
    48
  ///\param ItemIntMap A read and writable Item int map, used internally
alpar@1204
    49
  ///to handle the cross references.
jacint@857
    50
  ///\param Compare A class for the ordering of the priorities. The
jacint@857
    51
  ///default is \c std::less<Prio>.
jacint@857
    52
  ///
alpar@967
    53
  ///\sa BinHeap
alpar@967
    54
  ///\sa Dijkstra
jacint@857
    55
  ///\author Jacint Szabo 
jacint@857
    56
 
jacint@373
    57
#ifdef DOXYGEN
jacint@373
    58
  template <typename Item, 
jacint@373
    59
	    typename Prio, 
jacint@373
    60
	    typename ItemIntMap, 
jacint@373
    61
	    typename Compare>
jacint@373
    62
#else
jacint@373
    63
  template <typename Item, 
jacint@373
    64
	    typename Prio, 
jacint@373
    65
	    typename ItemIntMap, 
alpar@255
    66
	    typename Compare = std::less<Prio> >
jacint@373
    67
#endif
alpar@255
    68
  class FibHeap {
jacint@387
    69
  public:     
alpar@255
    70
    typedef Prio PrioType;
alpar@255
    71
    
jacint@373
    72
  private:
alpar@255
    73
    class store;
alpar@255
    74
    
alpar@255
    75
    std::vector<store> container;
alpar@255
    76
    int minimum;
alpar@255
    77
    ItemIntMap &iimap;
alpar@255
    78
    Compare comp;
alpar@255
    79
    int num_items;
jacint@373
    80
    
alpar@255
    81
  public:
alpar@1127
    82
    ///Status of the nodes
alpar@255
    83
    enum state_enum {
alpar@1127
    84
      ///The node is in the heap
alpar@255
    85
      IN_HEAP = 0,
alpar@1127
    86
      ///The node has never been in the heap
alpar@255
    87
      PRE_HEAP = -1,
alpar@1127
    88
      ///The node was in the heap but it got out of it
alpar@255
    89
      POST_HEAP = -2
alpar@255
    90
    };
alpar@255
    91
    
deba@1717
    92
    /// \brief The constructor
deba@1717
    93
    ///
deba@1717
    94
    /// \c _iimap should be given to the constructor, since it is
deba@1717
    95
    ///   used internally to handle the cross references.
deba@1185
    96
    explicit FibHeap(ItemIntMap &_iimap) 
deba@1185
    97
      : minimum(0), iimap(_iimap), num_items() {} 
jacint@1270
    98
 
deba@1717
    99
    /// \brief The constructor
deba@1717
   100
    ///
deba@1717
   101
    /// \c _iimap should be given to the constructor, since it is used
deba@1717
   102
    /// internally to handle the cross references. \c _comp is an
deba@1717
   103
    /// object for ordering of the priorities. 
jacint@373
   104
    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
jacint@1270
   105
		  iimap(_iimap), comp(_comp), num_items() {}
alpar@255
   106
    
deba@1717
   107
    /// \brief The number of items stored in the heap.
deba@1717
   108
    ///
deba@1717
   109
    /// Returns the number of items stored in the heap.
jacint@373
   110
    int size() const { return num_items; }
jacint@373
   111
deba@1717
   112
    /// \brief Checks if the heap stores no items.
deba@1717
   113
    ///
deba@1717
   114
    ///   Returns \c true if and only if the heap stores no items.
jacint@373
   115
    bool empty() const { return num_items==0; }
jacint@373
   116
deba@1717
   117
    /// \brief Make empty this heap.
deba@1717
   118
    /// 
deba@1717
   119
    /// Make empty this heap.
deba@1753
   120
    void clear() {
deba@1753
   121
      if (num_items != 0) {
deba@1753
   122
	for (int i = 0; i < (int)container.size(); ++i) {
deba@1753
   123
	  iimap[container[i].name] = -2;
deba@1753
   124
	}
deba@1717
   125
      }
deba@1717
   126
      container.clear(); minimum = 0; num_items = 0;
deba@1717
   127
    }
jacint@373
   128
deba@1717
   129
    /// \brief \c item gets to the heap with priority \c value independently 
deba@1717
   130
    /// if \c item was already there.
deba@1717
   131
    ///
deba@1717
   132
    /// This method calls \ref push(\c item, \c value) if \c item is not
deba@1717
   133
    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
deba@1717
   134
    /// \ref increase(\c item, \c value) otherwise.
jacint@387
   135
    void set (Item const item, PrioType const value); 
jacint@373
   136
    
deba@1717
   137
    /// \brief Adds \c item to the heap with priority \c value. 
deba@1717
   138
    ///    
deba@1717
   139
    /// Adds \c item to the heap with priority \c value. 
deba@1717
   140
    /// \pre \c item must not be stored in the heap. 
jacint@387
   141
    void push (Item const item, PrioType const value);
jacint@373
   142
    
deba@1717
   143
    /// \brief Returns the item with minimum priority relative to \c Compare.
deba@1717
   144
    ///
deba@1717
   145
    /// This method returns the item with minimum priority relative to \c
deba@1717
   146
    /// Compare.  
deba@1717
   147
    /// \pre The heap must be nonempty.  
jacint@373
   148
    Item top() const { return container[minimum].name; }
jacint@373
   149
deba@1717
   150
    /// \brief Returns the minimum priority relative to \c Compare.
deba@1717
   151
    ///
deba@1717
   152
    /// It returns the minimum priority relative to \c Compare.
deba@1717
   153
    /// \pre The heap must be nonempty.
jacint@373
   154
    PrioType prio() const { return container[minimum].prio; }
jacint@373
   155
    
deba@1717
   156
    /// \brief Returns the priority of \c item.
deba@1717
   157
    ///
deba@1717
   158
    /// This function returns the priority of \c item.
deba@1717
   159
    /// \pre \c item must be in the heap.
jacint@387
   160
    PrioType& operator[](const Item& item) { 
jacint@387
   161
      return container[iimap[item]].prio; 
jacint@387
   162
    }
jacint@373
   163
    
deba@1717
   164
    /// \brief Returns the priority of \c item.
deba@1717
   165
    ///
deba@1717
   166
    /// It returns the priority of \c item.
deba@1717
   167
    /// \pre \c item must be in the heap.
jacint@387
   168
    const PrioType& operator[](const Item& item) const { 
jacint@387
   169
      return container[iimap[item]].prio; 
alpar@255
   170
    }
alpar@255
   171
alpar@255
   172
deba@1717
   173
    /// \brief Deletes the item with minimum priority relative to \c Compare.
deba@1717
   174
    ///
deba@1717
   175
    /// This method deletes the item with minimum priority relative to \c
deba@1717
   176
    /// Compare from the heap.  
deba@1717
   177
    /// \pre The heap must be non-empty.  
jacint@373
   178
    void pop();
jacint@373
   179
deba@1717
   180
    /// \brief Deletes \c item from the heap.
deba@1717
   181
    ///
deba@1717
   182
    /// This method deletes \c item from the heap, if \c item was already
deba@1717
   183
    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
jacint@387
   184
    void erase (const Item& item); 
jacint@373
   185
deba@1717
   186
    /// \brief Decreases the priority of \c item to \c value.
deba@1717
   187
    ///
deba@1717
   188
    /// This method decreases the priority of \c item to \c value.
deba@1717
   189
    /// \pre \c item must be stored in the heap with priority at least \c
deba@1717
   190
    ///   value relative to \c Compare.
jacint@387
   191
    void decrease (Item item, PrioType const value); 
jacint@373
   192
deba@1717
   193
    /// \brief Increases the priority of \c item to \c value.
deba@1717
   194
    ///
deba@1717
   195
    /// This method sets the priority of \c item to \c value. Though
deba@1717
   196
    /// there is no precondition on the priority of \c item, this
deba@1717
   197
    /// method should be used only if it is indeed necessary to increase
deba@1717
   198
    /// (relative to \c Compare) the priority of \c item, because this
deba@1717
   199
    /// method is inefficient.
jacint@387
   200
    void increase (Item item, PrioType const value) {
jacint@387
   201
      erase(item);
jacint@387
   202
      push(item, value);
jacint@373
   203
    }
jacint@373
   204
jacint@373
   205
deba@1717
   206
    /// \brief Returns if \c item is in, has already been in, or has never 
deba@1717
   207
    /// been in the heap.
deba@1717
   208
    ///
deba@1717
   209
    /// This method returns PRE_HEAP if \c item has never been in the
deba@1717
   210
    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
deba@1717
   211
    /// otherwise. In the latter case it is possible that \c item will
deba@1717
   212
    /// get back to the heap again.
jacint@387
   213
    state_enum state(const Item &item) const {
jacint@387
   214
      int i=iimap[item];
jacint@387
   215
      if( i>=0 ) {
jacint@387
   216
	if ( container[i].in ) i=0;
jacint@387
   217
	else i=-2; 
jacint@387
   218
      }
jacint@387
   219
      return state_enum(i);
jacint@387
   220
    }    
deba@1902
   221
deba@1902
   222
    /// \brief Sets the state of the \c item in the heap.
deba@1902
   223
    ///
deba@1902
   224
    /// Sets the state of the \c item in the heap. It can be used to
deba@1902
   225
    /// manually clear the heap when it is important to achive the
deba@1902
   226
    /// better time complexity.
deba@1902
   227
    /// \param i The item.
deba@1902
   228
    /// \param st The state. It should not be \c IN_HEAP. 
deba@1902
   229
    void state(const Item& i, state_enum st) {
deba@1902
   230
      switch (st) {
deba@1902
   231
      case POST_HEAP:
deba@1902
   232
      case PRE_HEAP:
deba@1902
   233
        if (state(i) == IN_HEAP) {
deba@1902
   234
          erase(i);
deba@1902
   235
        }
deba@1903
   236
        iimap[i] = st;
deba@1902
   237
        break;
deba@1906
   238
      case IN_HEAP:
deba@1906
   239
        break;
deba@1902
   240
      }
deba@1902
   241
    }
jacint@387
   242
    
jacint@387
   243
  private:
jacint@387
   244
    
jacint@387
   245
    void balance();
jacint@387
   246
    void makeroot(int c);
jacint@387
   247
    void cut(int a, int b);
jacint@387
   248
    void cascade(int a);
jacint@387
   249
    void fuse(int a, int b);
jacint@387
   250
    void unlace(int a);
jacint@373
   251
jacint@373
   252
jacint@387
   253
    class store {
jacint@387
   254
      friend class FibHeap;
jacint@387
   255
      
jacint@387
   256
      Item name;
jacint@387
   257
      int parent;
jacint@387
   258
      int left_neighbor;
jacint@387
   259
      int right_neighbor;
jacint@387
   260
      int child;
jacint@387
   261
      int degree;  
jacint@387
   262
      bool marked;
jacint@387
   263
      bool in;
jacint@387
   264
      PrioType prio;
jacint@387
   265
      
jacint@387
   266
      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
jacint@387
   267
    };
jacint@387
   268
  };    
jacint@387
   269
 
jacint@387
   270
jacint@373
   271
jacint@373
   272
    // **********************************************************************
jacint@373
   273
    //  IMPLEMENTATIONS
jacint@373
   274
    // **********************************************************************
jacint@373
   275
    
jacint@387
   276
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   277
    typename Compare>
jacint@387
   278
  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
jacint@387
   279
  (Item const item, PrioType const value) 
jacint@387
   280
  {
jacint@387
   281
    int i=iimap[item];
jacint@387
   282
    if ( i >= 0 && container[i].in ) {
jacint@387
   283
      if ( comp(value, container[i].prio) ) decrease(item, value); 
jacint@387
   284
      if ( comp(container[i].prio, value) ) increase(item, value); 
jacint@387
   285
    } else push(item, value);
jacint@387
   286
  }
alpar@255
   287
    
jacint@387
   288
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   289
    typename Compare>
jacint@387
   290
  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
jacint@387
   291
  (Item const item, PrioType const value) {
jacint@387
   292
      int i=iimap[item];      
alpar@255
   293
      if ( i < 0 ) {
alpar@255
   294
	int s=container.size();
jacint@387
   295
	iimap.set( item, s );	
alpar@255
   296
	store st;
jacint@387
   297
	st.name=item;
alpar@255
   298
	container.push_back(st);
alpar@255
   299
	i=s;
alpar@255
   300
      } else {
alpar@255
   301
	container[i].parent=container[i].child=-1;
alpar@255
   302
	container[i].degree=0;
alpar@255
   303
	container[i].in=true;
alpar@255
   304
	container[i].marked=false;
alpar@255
   305
      }
alpar@255
   306
alpar@255
   307
      if ( num_items ) {
alpar@255
   308
	container[container[minimum].right_neighbor].left_neighbor=i;
alpar@255
   309
	container[i].right_neighbor=container[minimum].right_neighbor;
alpar@255
   310
	container[minimum].right_neighbor=i;
alpar@255
   311
	container[i].left_neighbor=minimum;
alpar@255
   312
	if ( comp( value, container[minimum].prio) ) minimum=i; 
alpar@255
   313
      } else {
alpar@255
   314
	container[i].right_neighbor=container[i].left_neighbor=i;
alpar@255
   315
	minimum=i;	
alpar@255
   316
      }
alpar@255
   317
      container[i].prio=value;
alpar@255
   318
      ++num_items;
alpar@255
   319
    }
alpar@255
   320
    
jacint@387
   321
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   322
    typename Compare>
jacint@387
   323
  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
alpar@255
   324
      /*The first case is that there are only one root.*/
alpar@255
   325
      if ( container[minimum].left_neighbor==minimum ) {
alpar@255
   326
	container[minimum].in=false;
alpar@255
   327
	if ( container[minimum].degree!=0 ) { 
alpar@255
   328
	  makeroot(container[minimum].child);
alpar@255
   329
	  minimum=container[minimum].child;
alpar@255
   330
	  balance();
alpar@255
   331
	}
alpar@255
   332
      } else {
alpar@255
   333
	int right=container[minimum].right_neighbor;
alpar@255
   334
	unlace(minimum);
alpar@255
   335
	container[minimum].in=false;
alpar@255
   336
	if ( container[minimum].degree > 0 ) {
alpar@255
   337
	  int left=container[minimum].left_neighbor;
alpar@255
   338
	  int child=container[minimum].child;
alpar@255
   339
	  int last_child=container[child].left_neighbor;
alpar@255
   340
	
alpar@255
   341
	  makeroot(child);
alpar@255
   342
	  
alpar@255
   343
	  container[left].right_neighbor=child;
alpar@255
   344
	  container[child].left_neighbor=left;
alpar@255
   345
	  container[right].left_neighbor=last_child;
alpar@255
   346
	  container[last_child].right_neighbor=right;
alpar@255
   347
	}
alpar@255
   348
	minimum=right;
alpar@255
   349
	balance();
alpar@255
   350
      } // the case where there are more roots
alpar@255
   351
      --num_items;   
alpar@255
   352
    }
alpar@255
   353
jacint@387
   354
jacint@387
   355
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   356
    typename Compare>
jacint@387
   357
  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
jacint@387
   358
  (const Item& item) {
jacint@387
   359
      int i=iimap[item];
alpar@255
   360
      
alpar@255
   361
      if ( i >= 0 && container[i].in ) { 	
alpar@255
   362
	if ( container[i].parent!=-1 ) {
alpar@255
   363
	  int p=container[i].parent;
alpar@255
   364
	  cut(i,p);	    
alpar@255
   365
	  cascade(p);
alpar@255
   366
	}
alpar@255
   367
	minimum=i;     //As if its prio would be -infinity
alpar@255
   368
	pop();
alpar@255
   369
      }
jacint@387
   370
  }
alpar@255
   371
    
jacint@387
   372
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   373
    typename Compare>
jacint@387
   374
  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
jacint@387
   375
  (Item item, PrioType const value) {
jacint@387
   376
      int i=iimap[item];
alpar@255
   377
      container[i].prio=value;
alpar@255
   378
      int p=container[i].parent;
alpar@255
   379
      
alpar@255
   380
      if ( p!=-1 && comp(value, container[p].prio) ) {
alpar@255
   381
	cut(i,p);	    
alpar@255
   382
	cascade(p);
alpar@255
   383
      }      
alpar@255
   384
      if ( comp(value, container[minimum].prio) ) minimum=i; 
jacint@387
   385
  }
jacint@387
   386
 
alpar@255
   387
jacint@387
   388
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   389
    typename Compare>
jacint@387
   390
  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
alpar@255
   391
deba@1332
   392
    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
alpar@255
   393
  
alpar@255
   394
    std::vector<int> A(maxdeg,-1); 
alpar@255
   395
    
alpar@255
   396
    /*
alpar@255
   397
     *Recall that now minimum does not point to the minimum prio element.
alpar@255
   398
     *We set minimum to this during balance().
alpar@255
   399
     */
alpar@255
   400
    int anchor=container[minimum].left_neighbor; 
alpar@255
   401
    int next=minimum; 
alpar@255
   402
    bool end=false; 
alpar@255
   403
    	
alpar@255
   404
       do {
alpar@255
   405
	int active=next;
alpar@255
   406
	if ( anchor==active ) end=true;
alpar@255
   407
	int d=container[active].degree;
alpar@255
   408
	next=container[active].right_neighbor;
alpar@255
   409
alpar@255
   410
	while (A[d]!=-1) {	  
alpar@255
   411
	  if( comp(container[active].prio, container[A[d]].prio) ) {
alpar@255
   412
	    fuse(active,A[d]); 
alpar@255
   413
	  } else { 
alpar@255
   414
	    fuse(A[d],active);
alpar@255
   415
	    active=A[d];
alpar@255
   416
	  } 
alpar@255
   417
	  A[d]=-1;
alpar@255
   418
	  ++d;
alpar@255
   419
	}	
alpar@255
   420
	A[d]=active;
alpar@255
   421
       } while ( !end );
alpar@255
   422
alpar@255
   423
alpar@255
   424
       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
alpar@255
   425
       int s=minimum;
alpar@255
   426
       int m=minimum;
alpar@255
   427
       do {  
alpar@255
   428
	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
alpar@255
   429
	 s=container[s].right_neighbor;
alpar@255
   430
       } while ( s != m );
alpar@255
   431
    }
alpar@255
   432
jacint@387
   433
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   434
    typename Compare>
jacint@387
   435
  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
jacint@387
   436
  (int c) {
alpar@255
   437
      int s=c;
alpar@255
   438
      do {  
alpar@255
   439
	container[s].parent=-1;
alpar@255
   440
	s=container[s].right_neighbor;
alpar@255
   441
      } while ( s != c );
alpar@255
   442
    }
jacint@387
   443
  
jacint@387
   444
  
jacint@387
   445
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   446
    typename Compare>
jacint@387
   447
  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
jacint@387
   448
  (int a, int b) {    
jacint@387
   449
    /*
jacint@387
   450
     *Replacing a from the children of b.
jacint@387
   451
     */
jacint@387
   452
    --container[b].degree;
alpar@255
   453
    
jacint@387
   454
    if ( container[b].degree !=0 ) {
jacint@387
   455
      int child=container[b].child;
jacint@387
   456
      if ( child==a ) 
jacint@387
   457
	container[b].child=container[child].right_neighbor;
jacint@387
   458
      unlace(a);
jacint@387
   459
    }
jacint@387
   460
    
jacint@387
   461
    
jacint@387
   462
    /*Lacing a to the roots.*/
jacint@387
   463
    int right=container[minimum].right_neighbor;
jacint@387
   464
    container[minimum].right_neighbor=a;
jacint@387
   465
    container[a].left_neighbor=minimum;
jacint@387
   466
    container[a].right_neighbor=right;
jacint@387
   467
    container[right].left_neighbor=a;
jacint@387
   468
    
jacint@387
   469
    container[a].parent=-1;
jacint@387
   470
    container[a].marked=false;
jacint@387
   471
  }
jacint@387
   472
  
alpar@255
   473
jacint@387
   474
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   475
    typename Compare>
jacint@387
   476
  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
jacint@387
   477
  (int a) 
alpar@255
   478
    {
alpar@255
   479
      if ( container[a].parent!=-1 ) {
alpar@255
   480
	int p=container[a].parent;
alpar@255
   481
	
alpar@255
   482
	if ( container[a].marked==false ) container[a].marked=true;
alpar@255
   483
	else {
alpar@255
   484
	  cut(a,p);
alpar@255
   485
	  cascade(p);
alpar@255
   486
	}
alpar@255
   487
      }
alpar@255
   488
    }
alpar@255
   489
alpar@255
   490
jacint@387
   491
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   492
    typename Compare>
jacint@387
   493
  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
jacint@387
   494
  (int a, int b) {
alpar@255
   495
      unlace(b);
alpar@255
   496
      
alpar@255
   497
      /*Lacing b under a.*/
alpar@255
   498
      container[b].parent=a;
alpar@255
   499
alpar@255
   500
      if (container[a].degree==0) {
alpar@255
   501
	container[b].left_neighbor=b;
alpar@255
   502
	container[b].right_neighbor=b;
alpar@255
   503
	container[a].child=b;	
alpar@255
   504
      } else {
alpar@255
   505
	int child=container[a].child;
alpar@255
   506
	int last_child=container[child].left_neighbor;
alpar@255
   507
	container[child].left_neighbor=b;
alpar@255
   508
	container[b].right_neighbor=child;
alpar@255
   509
	container[last_child].right_neighbor=b;
alpar@255
   510
	container[b].left_neighbor=last_child;
alpar@255
   511
      }
alpar@255
   512
alpar@255
   513
      ++container[a].degree;
alpar@255
   514
      
alpar@255
   515
      container[b].marked=false;
alpar@255
   516
    }
alpar@255
   517
jacint@387
   518
  
jacint@387
   519
  /*
jacint@387
   520
   *It is invoked only if a has siblings.
jacint@387
   521
   */
jacint@387
   522
  template <typename Item, typename Prio, typename ItemIntMap, 
jacint@387
   523
    typename Compare>
jacint@387
   524
  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
jacint@387
   525
  (int a) {      
alpar@255
   526
      int leftn=container[a].left_neighbor;
alpar@255
   527
      int rightn=container[a].right_neighbor;
alpar@255
   528
      container[leftn].right_neighbor=rightn;
alpar@255
   529
      container[rightn].left_neighbor=leftn;
jacint@387
   530
  }
alpar@255
   531
  
alpar@430
   532
alpar@921
   533
} //namespace lemon
alpar@477
   534
alpar@921
   535
#endif //LEMON_FIB_HEAP_H
alpar@477
   536