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