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