lemon/bin_heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 209 765619b7cbb2
child 559 c5fd2d996909
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@100
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@100
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@100
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100
     8
 *
alpar@100
     9
 * Permission to use, modify and distribute this software is granted
alpar@100
    10
 * provided that this copyright notice appears in all copies. For
alpar@100
    11
 * precise terms see the accompanying LICENSE file.
alpar@100
    12
 *
alpar@100
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@100
    14
 * express or implied, and with no claim as to its suitability for any
alpar@100
    15
 * purpose.
alpar@100
    16
 *
alpar@100
    17
 */
alpar@100
    18
alpar@100
    19
#ifndef LEMON_BIN_HEAP_H
alpar@100
    20
#define LEMON_BIN_HEAP_H
alpar@100
    21
alpar@100
    22
///\ingroup auxdat
alpar@100
    23
///\file
alpar@100
    24
///\brief Binary Heap implementation.
alpar@100
    25
alpar@100
    26
#include <vector>
alpar@100
    27
#include <utility>
alpar@100
    28
#include <functional>
alpar@100
    29
alpar@100
    30
namespace lemon {
alpar@100
    31
alpar@100
    32
  ///\ingroup auxdat
alpar@100
    33
  ///
alpar@100
    34
  ///\brief A Binary Heap implementation.
alpar@100
    35
  ///
alpar@100
    36
  ///This class implements the \e binary \e heap data structure. A \e heap
alpar@100
    37
  ///is a data structure for storing items with specified values called \e
alpar@100
    38
  ///priorities in such a way that finding the item with minimum priority is
alpar@100
    39
  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
alpar@100
    40
  ///one can change the priority of an item, add or erase an item, etc.
alpar@100
    41
  ///
kpeter@157
    42
  ///\tparam _Prio Type of the priority of the items.
kpeter@157
    43
  ///\tparam _ItemIntMap A read and writable Item int map, used internally
alpar@100
    44
  ///to handle the cross references.
kpeter@157
    45
  ///\tparam _Compare A class for the ordering of the priorities. The
alpar@100
    46
  ///default is \c std::less<_Prio>.
alpar@100
    47
  ///
alpar@100
    48
  ///\sa FibHeap
alpar@100
    49
  ///\sa Dijkstra
alpar@100
    50
  template <typename _Prio, typename _ItemIntMap,
alpar@209
    51
            typename _Compare = std::less<_Prio> >
alpar@100
    52
  class BinHeap {
alpar@100
    53
alpar@100
    54
  public:
alpar@100
    55
    ///\e
alpar@100
    56
    typedef _ItemIntMap ItemIntMap;
alpar@100
    57
    ///\e
alpar@100
    58
    typedef _Prio Prio;
alpar@100
    59
    ///\e
alpar@100
    60
    typedef typename ItemIntMap::Key Item;
alpar@100
    61
    ///\e
alpar@100
    62
    typedef std::pair<Item,Prio> Pair;
alpar@100
    63
    ///\e
alpar@100
    64
    typedef _Compare Compare;
alpar@100
    65
alpar@100
    66
    /// \brief Type to represent the items states.
alpar@100
    67
    ///
alpar@100
    68
    /// Each Item element have a state associated to it. It may be "in heap",
alpar@100
    69
    /// "pre heap" or "post heap". The latter two are indifferent from the
alpar@100
    70
    /// heap's point of view, but may be useful to the user.
alpar@100
    71
    ///
alpar@100
    72
    /// The ItemIntMap \e should be initialized in such way that it maps
alpar@100
    73
    /// PRE_HEAP (-1) to any element to be put in the heap...
alpar@100
    74
    enum State {
alpar@100
    75
      IN_HEAP = 0,
alpar@100
    76
      PRE_HEAP = -1,
alpar@100
    77
      POST_HEAP = -2
alpar@100
    78
    };
alpar@100
    79
alpar@100
    80
  private:
alpar@100
    81
    std::vector<Pair> data;
alpar@100
    82
    Compare comp;
alpar@100
    83
    ItemIntMap &iim;
alpar@100
    84
alpar@100
    85
  public:
alpar@100
    86
    /// \brief The constructor.
alpar@100
    87
    ///
alpar@100
    88
    /// The constructor.
alpar@100
    89
    /// \param _iim should be given to the constructor, since it is used
alpar@100
    90
    /// internally to handle the cross references. The value of the map
alpar@100
    91
    /// should be PRE_HEAP (-1) for each element.
alpar@100
    92
    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
alpar@209
    93
alpar@100
    94
    /// \brief The constructor.
alpar@100
    95
    ///
alpar@100
    96
    /// The constructor.
alpar@100
    97
    /// \param _iim should be given to the constructor, since it is used
alpar@100
    98
    /// internally to handle the cross references. The value of the map
alpar@100
    99
    /// should be PRE_HEAP (-1) for each element.
alpar@100
   100
    ///
alpar@100
   101
    /// \param _comp The comparator function object.
alpar@209
   102
    BinHeap(ItemIntMap &_iim, const Compare &_comp)
alpar@100
   103
      : iim(_iim), comp(_comp) {}
alpar@100
   104
alpar@100
   105
alpar@100
   106
    /// The number of items stored in the heap.
alpar@100
   107
    ///
alpar@100
   108
    /// \brief Returns the number of items stored in the heap.
alpar@100
   109
    int size() const { return data.size(); }
alpar@209
   110
alpar@100
   111
    /// \brief Checks if the heap stores no items.
alpar@100
   112
    ///
alpar@100
   113
    /// Returns \c true if and only if the heap stores no items.
alpar@100
   114
    bool empty() const { return data.empty(); }
alpar@100
   115
alpar@100
   116
    /// \brief Make empty this heap.
alpar@209
   117
    ///
alpar@100
   118
    /// Make empty this heap. It does not change the cross reference map.
alpar@100
   119
    /// If you want to reuse what is not surely empty you should first clear
alpar@100
   120
    /// the heap and after that you should set the cross reference map for
alpar@100
   121
    /// each item to \c PRE_HEAP.
alpar@209
   122
    void clear() {
alpar@209
   123
      data.clear();
alpar@100
   124
    }
alpar@100
   125
alpar@100
   126
  private:
alpar@100
   127
    static int parent(int i) { return (i-1)/2; }
alpar@100
   128
alpar@100
   129
    static int second_child(int i) { return 2*i+2; }
alpar@100
   130
    bool less(const Pair &p1, const Pair &p2) const {
alpar@100
   131
      return comp(p1.second, p2.second);
alpar@100
   132
    }
alpar@100
   133
alpar@100
   134
    int bubble_up(int hole, Pair p) {
alpar@100
   135
      int par = parent(hole);
alpar@100
   136
      while( hole>0 && less(p,data[par]) ) {
alpar@209
   137
        move(data[par],hole);
alpar@209
   138
        hole = par;
alpar@209
   139
        par = parent(hole);
alpar@100
   140
      }
alpar@100
   141
      move(p, hole);
alpar@100
   142
      return hole;
alpar@100
   143
    }
alpar@100
   144
alpar@100
   145
    int bubble_down(int hole, Pair p, int length) {
alpar@100
   146
      int child = second_child(hole);
alpar@100
   147
      while(child < length) {
alpar@209
   148
        if( less(data[child-1], data[child]) ) {
alpar@209
   149
          --child;
alpar@209
   150
        }
alpar@209
   151
        if( !less(data[child], p) )
alpar@209
   152
          goto ok;
alpar@209
   153
        move(data[child], hole);
alpar@209
   154
        hole = child;
alpar@209
   155
        child = second_child(hole);
alpar@100
   156
      }
alpar@100
   157
      child--;
alpar@100
   158
      if( child<length && less(data[child], p) ) {
alpar@209
   159
        move(data[child], hole);
alpar@209
   160
        hole=child;
alpar@100
   161
      }
alpar@100
   162
    ok:
alpar@100
   163
      move(p, hole);
alpar@100
   164
      return hole;
alpar@100
   165
    }
alpar@100
   166
alpar@100
   167
    void move(const Pair &p, int i) {
alpar@100
   168
      data[i] = p;
alpar@100
   169
      iim.set(p.first, i);
alpar@100
   170
    }
alpar@100
   171
alpar@100
   172
  public:
alpar@100
   173
    /// \brief Insert a pair of item and priority into the heap.
alpar@100
   174
    ///
alpar@100
   175
    /// Adds \c p.first to the heap with priority \c p.second.
alpar@100
   176
    /// \param p The pair to insert.
alpar@100
   177
    void push(const Pair &p) {
alpar@100
   178
      int n = data.size();
alpar@100
   179
      data.resize(n+1);
alpar@100
   180
      bubble_up(n, p);
alpar@100
   181
    }
alpar@100
   182
alpar@100
   183
    /// \brief Insert an item into the heap with the given heap.
alpar@209
   184
    ///
alpar@209
   185
    /// Adds \c i to the heap with priority \c p.
alpar@100
   186
    /// \param i The item to insert.
alpar@100
   187
    /// \param p The priority of the item.
alpar@100
   188
    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
alpar@100
   189
alpar@100
   190
    /// \brief Returns the item with minimum priority relative to \c Compare.
alpar@100
   191
    ///
alpar@100
   192
    /// This method returns the item with minimum priority relative to \c
alpar@209
   193
    /// Compare.
alpar@209
   194
    /// \pre The heap must be nonempty.
alpar@100
   195
    Item top() const {
alpar@100
   196
      return data[0].first;
alpar@100
   197
    }
alpar@100
   198
alpar@100
   199
    /// \brief Returns the minimum priority relative to \c Compare.
alpar@100
   200
    ///
alpar@100
   201
    /// It returns the minimum priority relative to \c Compare.
alpar@100
   202
    /// \pre The heap must be nonempty.
alpar@100
   203
    Prio prio() const {
alpar@100
   204
      return data[0].second;
alpar@100
   205
    }
alpar@100
   206
alpar@100
   207
    /// \brief Deletes the item with minimum priority relative to \c Compare.
alpar@100
   208
    ///
alpar@100
   209
    /// This method deletes the item with minimum priority relative to \c
alpar@209
   210
    /// Compare from the heap.
alpar@209
   211
    /// \pre The heap must be non-empty.
alpar@100
   212
    void pop() {
alpar@100
   213
      int n = data.size()-1;
alpar@100
   214
      iim.set(data[0].first, POST_HEAP);
alpar@100
   215
      if (n > 0) {
alpar@209
   216
        bubble_down(0, data[n], n);
alpar@100
   217
      }
alpar@100
   218
      data.pop_back();
alpar@100
   219
    }
alpar@100
   220
alpar@100
   221
    /// \brief Deletes \c i from the heap.
alpar@100
   222
    ///
alpar@100
   223
    /// This method deletes item \c i from the heap.
alpar@100
   224
    /// \param i The item to erase.
alpar@100
   225
    /// \pre The item should be in the heap.
alpar@100
   226
    void erase(const Item &i) {
alpar@100
   227
      int h = iim[i];
alpar@100
   228
      int n = data.size()-1;
alpar@100
   229
      iim.set(data[h].first, POST_HEAP);
alpar@100
   230
      if( h < n ) {
alpar@209
   231
        if ( bubble_up(h, data[n]) == h) {
alpar@209
   232
          bubble_down(h, data[n], n);
alpar@209
   233
        }
alpar@100
   234
      }
alpar@100
   235
      data.pop_back();
alpar@100
   236
    }
alpar@100
   237
alpar@209
   238
alpar@100
   239
    /// \brief Returns the priority of \c i.
alpar@100
   240
    ///
alpar@209
   241
    /// This function returns the priority of item \c i.
alpar@100
   242
    /// \pre \c i must be in the heap.
alpar@100
   243
    /// \param i The item.
alpar@100
   244
    Prio operator[](const Item &i) const {
alpar@100
   245
      int idx = iim[i];
alpar@100
   246
      return data[idx].second;
alpar@100
   247
    }
alpar@100
   248
alpar@209
   249
    /// \brief \c i gets to the heap with priority \c p independently
alpar@100
   250
    /// if \c i was already there.
alpar@100
   251
    ///
alpar@100
   252
    /// This method calls \ref push(\c i, \c p) if \c i is not stored
alpar@100
   253
    /// in the heap and sets the priority of \c i to \c p otherwise.
alpar@100
   254
    /// \param i The item.
alpar@100
   255
    /// \param p The priority.
alpar@100
   256
    void set(const Item &i, const Prio &p) {
alpar@100
   257
      int idx = iim[i];
alpar@100
   258
      if( idx < 0 ) {
alpar@209
   259
        push(i,p);
alpar@100
   260
      }
alpar@100
   261
      else if( comp(p, data[idx].second) ) {
alpar@209
   262
        bubble_up(idx, Pair(i,p));
alpar@100
   263
      }
alpar@100
   264
      else {
alpar@209
   265
        bubble_down(idx, Pair(i,p), data.size());
alpar@100
   266
      }
alpar@100
   267
    }
alpar@100
   268
alpar@100
   269
    /// \brief Decreases the priority of \c i to \c p.
alpar@100
   270
    ///
alpar@100
   271
    /// This method decreases the priority of item \c i to \c p.
alpar@100
   272
    /// \pre \c i must be stored in the heap with priority at least \c
alpar@100
   273
    /// p relative to \c Compare.
alpar@100
   274
    /// \param i The item.
alpar@100
   275
    /// \param p The priority.
alpar@100
   276
    void decrease(const Item &i, const Prio &p) {
alpar@100
   277
      int idx = iim[i];
alpar@100
   278
      bubble_up(idx, Pair(i,p));
alpar@100
   279
    }
alpar@209
   280
alpar@100
   281
    /// \brief Increases the priority of \c i to \c p.
alpar@100
   282
    ///
alpar@209
   283
    /// This method sets the priority of item \c i to \c p.
alpar@100
   284
    /// \pre \c i must be stored in the heap with priority at most \c
alpar@100
   285
    /// p relative to \c Compare.
alpar@100
   286
    /// \param i The item.
alpar@100
   287
    /// \param p The priority.
alpar@100
   288
    void increase(const Item &i, const Prio &p) {
alpar@100
   289
      int idx = iim[i];
alpar@100
   290
      bubble_down(idx, Pair(i,p), data.size());
alpar@100
   291
    }
alpar@100
   292
alpar@209
   293
    /// \brief Returns if \c item is in, has already been in, or has
alpar@100
   294
    /// never been in the heap.
alpar@100
   295
    ///
alpar@100
   296
    /// This method returns PRE_HEAP if \c item has never been in the
alpar@100
   297
    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
alpar@100
   298
    /// otherwise. In the latter case it is possible that \c item will
alpar@100
   299
    /// get back to the heap again.
alpar@100
   300
    /// \param i The item.
alpar@100
   301
    State state(const Item &i) const {
alpar@100
   302
      int s = iim[i];
alpar@100
   303
      if( s>=0 )
alpar@209
   304
        s=0;
alpar@100
   305
      return State(s);
alpar@100
   306
    }
alpar@100
   307
alpar@100
   308
    /// \brief Sets the state of the \c item in the heap.
alpar@100
   309
    ///
alpar@100
   310
    /// Sets the state of the \c item in the heap. It can be used to
alpar@100
   311
    /// manually clear the heap when it is important to achive the
alpar@100
   312
    /// better time complexity.
alpar@100
   313
    /// \param i The item.
alpar@209
   314
    /// \param st The state. It should not be \c IN_HEAP.
alpar@100
   315
    void state(const Item& i, State st) {
alpar@100
   316
      switch (st) {
alpar@100
   317
      case POST_HEAP:
alpar@100
   318
      case PRE_HEAP:
alpar@100
   319
        if (state(i) == IN_HEAP) {
alpar@100
   320
          erase(i);
alpar@100
   321
        }
alpar@100
   322
        iim[i] = st;
alpar@100
   323
        break;
alpar@100
   324
      case IN_HEAP:
alpar@100
   325
        break;
alpar@100
   326
      }
alpar@100
   327
    }
alpar@100
   328
alpar@100
   329
    /// \brief Replaces an item in the heap.
alpar@100
   330
    ///
alpar@100
   331
    /// The \c i item is replaced with \c j item. The \c i item should
alpar@100
   332
    /// be in the heap, while the \c j should be out of the heap. The
alpar@100
   333
    /// \c i item will out of the heap and \c j will be in the heap
alpar@100
   334
    /// with the same prioriority as prevoiusly the \c i item.
alpar@100
   335
    void replace(const Item& i, const Item& j) {
alpar@100
   336
      int idx = iim[i];
alpar@100
   337
      iim.set(i, iim[j]);
alpar@100
   338
      iim.set(j, idx);
alpar@100
   339
      data[idx].first = j;
alpar@100
   340
    }
alpar@100
   341
alpar@100
   342
  }; // class BinHeap
alpar@209
   343
alpar@100
   344
} // namespace lemon
alpar@100
   345
alpar@100
   346
#endif // LEMON_BIN_HEAP_H