lemon/bin_heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 09 Oct 2008 22:41:29 +0200
changeset 318 1e2d6ca80793
parent 157 2ccc1afc2c52
child 463 88ed40ad0d4f
permissions -rw-r--r--
Doc improvements
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@100
     5
 * Copyright (C) 2003-2008
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