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