1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/binom_heap.h Thu Jul 09 02:38:01 2009 +0200
1.3 @@ -0,0 +1,506 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BINOM_HEAP_H
1.23 +#define LEMON_BINOM_HEAP_H
1.24 +
1.25 +///\file
1.26 +///\ingroup auxdat
1.27 +///\brief Binomial Heap implementation.
1.28 +
1.29 +#include <vector>
1.30 +#include <functional>
1.31 +#include <lemon/math.h>
1.32 +#include <lemon/counter.h>
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + /// \ingroup auxdat
1.37 + ///
1.38 + ///\brief Binomial Heap.
1.39 + ///
1.40 + ///This class implements the \e Binomial \e heap data structure. A \e heap
1.41 + ///is a data structure for storing items with specified values called \e
1.42 + ///priorities in such a way that finding the item with minimum priority is
1.43 + ///efficient. \c Compare specifies the ordering of the priorities. In a heap
1.44 + ///one can change the priority of an item, add or erase an item, etc.
1.45 + ///
1.46 + ///The methods \ref increase and \ref erase are not efficient in a Binomial
1.47 + ///heap. In case of many calls to these operations, it is better to use a
1.48 + ///\ref BinHeap "binary heap".
1.49 + ///
1.50 + ///\param _Prio Type of the priority of the items.
1.51 + ///\param _ItemIntMap A read and writable Item int map, used internally
1.52 + ///to handle the cross references.
1.53 + ///\param _Compare A class for the ordering of the priorities. The
1.54 + ///default is \c std::less<_Prio>.
1.55 + ///
1.56 + ///\sa BinHeap
1.57 + ///\sa Dijkstra
1.58 + ///\author Dorian Batha
1.59 +
1.60 +#ifdef DOXYGEN
1.61 + template <typename _Prio,
1.62 + typename _ItemIntMap,
1.63 + typename _Compare>
1.64 +#else
1.65 + template <typename _Prio,
1.66 + typename _ItemIntMap,
1.67 + typename _Compare = std::less<_Prio> >
1.68 +#endif
1.69 + class BinomHeap {
1.70 + public:
1.71 + typedef _ItemIntMap ItemIntMap;
1.72 + typedef _Prio Prio;
1.73 + typedef typename ItemIntMap::Key Item;
1.74 + typedef std::pair<Item,Prio> Pair;
1.75 + typedef _Compare Compare;
1.76 +
1.77 + private:
1.78 + class store;
1.79 +
1.80 + std::vector<store> container;
1.81 + int minimum, head;
1.82 + ItemIntMap &iimap;
1.83 + Compare comp;
1.84 + int num_items;
1.85 +
1.86 + public:
1.87 + ///Status of the nodes
1.88 + enum State {
1.89 + ///The node is in the heap
1.90 + IN_HEAP = 0,
1.91 + ///The node has never been in the heap
1.92 + PRE_HEAP = -1,
1.93 + ///The node was in the heap but it got out of it
1.94 + POST_HEAP = -2
1.95 + };
1.96 +
1.97 + /// \brief The constructor
1.98 + ///
1.99 + /// \c _iimap should be given to the constructor, since it is
1.100 + /// used internally to handle the cross references.
1.101 + explicit BinomHeap(ItemIntMap &_iimap)
1.102 + : minimum(0), head(-1), iimap(_iimap), num_items() {}
1.103 +
1.104 + /// \brief The constructor
1.105 + ///
1.106 + /// \c _iimap should be given to the constructor, since it is used
1.107 + /// internally to handle the cross references. \c _comp is an
1.108 + /// object for ordering of the priorities.
1.109 + BinomHeap(ItemIntMap &_iimap, const Compare &_comp)
1.110 + : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {}
1.111 +
1.112 + /// \brief The number of items stored in the heap.
1.113 + ///
1.114 + /// Returns the number of items stored in the heap.
1.115 + int size() const { return num_items; }
1.116 +
1.117 + /// \brief Checks if the heap stores no items.
1.118 + ///
1.119 + /// Returns \c true if and only if the heap stores no items.
1.120 + bool empty() const { return num_items==0; }
1.121 +
1.122 + /// \brief Make empty this heap.
1.123 + ///
1.124 + /// Make empty this heap. It does not change the cross reference
1.125 + /// map. If you want to reuse a heap what is not surely empty you
1.126 + /// should first clear the heap and after that you should set the
1.127 + /// cross reference map for each item to \c PRE_HEAP.
1.128 + void clear() {
1.129 + container.clear(); minimum=0; num_items=0; head=-1;
1.130 + }
1.131 +
1.132 + /// \brief \c item gets to the heap with priority \c value independently
1.133 + /// if \c item was already there.
1.134 + ///
1.135 + /// This method calls \ref push(\c item, \c value) if \c item is not
1.136 + /// stored in the heap and it calls \ref decrease(\c item, \c value) or
1.137 + /// \ref increase(\c item, \c value) otherwise.
1.138 + void set (const Item& item, const Prio& value) {
1.139 + int i=iimap[item];
1.140 + if ( i >= 0 && container[i].in ) {
1.141 + if ( comp(value, container[i].prio) ) decrease(item, value);
1.142 + if ( comp(container[i].prio, value) ) increase(item, value);
1.143 + } else push(item, value);
1.144 + }
1.145 +
1.146 + /// \brief Adds \c item to the heap with priority \c value.
1.147 + ///
1.148 + /// Adds \c item to the heap with priority \c value.
1.149 + /// \pre \c item must not be stored in the heap.
1.150 + void push (const Item& item, const Prio& value) {
1.151 + int i=iimap[item];
1.152 + if ( i<0 ) {
1.153 + int s=container.size();
1.154 + iimap.set( item,s );
1.155 + store st;
1.156 + st.name=item;
1.157 + container.push_back(st);
1.158 + i=s;
1.159 + }
1.160 + else {
1.161 + container[i].parent=container[i].right_neighbor=container[i].child=-1;
1.162 + container[i].degree=0;
1.163 + container[i].in=true;
1.164 + }
1.165 + container[i].prio=value;
1.166 +
1.167 + if( 0==num_items ) { head=i; minimum=i; }
1.168 + else { merge(i); }
1.169 +
1.170 + minimum = find_min();
1.171 +
1.172 + ++num_items;
1.173 + }
1.174 +
1.175 + /// \brief Returns the item with minimum priority relative to \c Compare.
1.176 + ///
1.177 + /// This method returns the item with minimum priority relative to \c
1.178 + /// Compare.
1.179 + /// \pre The heap must be nonempty.
1.180 + Item top() const { return container[minimum].name; }
1.181 +
1.182 + /// \brief Returns the minimum priority relative to \c Compare.
1.183 + ///
1.184 + /// It returns the minimum priority relative to \c Compare.
1.185 + /// \pre The heap must be nonempty.
1.186 + const Prio& prio() const { return container[minimum].prio; }
1.187 +
1.188 + /// \brief Returns the priority of \c item.
1.189 + ///
1.190 + /// It returns the priority of \c item.
1.191 + /// \pre \c item must be in the heap.
1.192 + const Prio& operator[](const Item& item) const {
1.193 + return container[iimap[item]].prio;
1.194 + }
1.195 +
1.196 + /// \brief Deletes the item with minimum priority relative to \c Compare.
1.197 + ///
1.198 + /// This method deletes the item with minimum priority relative to \c
1.199 + /// Compare from the heap.
1.200 + /// \pre The heap must be non-empty.
1.201 + void pop() {
1.202 + container[minimum].in=false;
1.203 +
1.204 + int head_child=-1;
1.205 + if ( container[minimum].child!=-1 ) {
1.206 + int child=container[minimum].child;
1.207 + int neighb;
1.208 + int prev=-1;
1.209 + while( child!=-1 ) {
1.210 + neighb=container[child].right_neighbor;
1.211 + container[child].parent=-1;
1.212 + container[child].right_neighbor=prev;
1.213 + head_child=child;
1.214 + prev=child;
1.215 + child=neighb;
1.216 + }
1.217 + }
1.218 +
1.219 + // The first case is that there are only one root.
1.220 + if ( -1==container[head].right_neighbor ) {
1.221 + head=head_child;
1.222 + }
1.223 + // The case where there are more roots.
1.224 + else {
1.225 + if( head!=minimum ) { unlace(minimum); }
1.226 + else { head=container[head].right_neighbor; }
1.227 +
1.228 + merge(head_child);
1.229 + }
1.230 + minimum=find_min();
1.231 + --num_items;
1.232 + }
1.233 +
1.234 + /// \brief Deletes \c item from the heap.
1.235 + ///
1.236 + /// This method deletes \c item from the heap, if \c item was already
1.237 + /// stored in the heap. It is quite inefficient in Binomial heaps.
1.238 + void erase (const Item& item) {
1.239 + int i=iimap[item];
1.240 + if ( i >= 0 && container[i].in ) {
1.241 + decrease( item, container[minimum].prio-1 );
1.242 + pop();
1.243 + }
1.244 + }
1.245 +
1.246 + /// \brief Decreases the priority of \c item to \c value.
1.247 + ///
1.248 + /// This method decreases the priority of \c item to \c value.
1.249 + /// \pre \c item must be stored in the heap with priority at least \c
1.250 + /// value relative to \c Compare.
1.251 + void decrease (Item item, const Prio& value) {
1.252 + int i=iimap[item];
1.253 +
1.254 + if( comp( value,container[i].prio ) ) {
1.255 + container[i].prio=value;
1.256 +
1.257 + int p_loc=container[i].parent, loc=i;
1.258 + int parent, child, neighb;
1.259 +
1.260 + while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {
1.261 +
1.262 + // parent set for other loc_child
1.263 + child=container[loc].child;
1.264 + while( -1!=child ) {
1.265 + container[child].parent=p_loc;
1.266 + child=container[child].right_neighbor;
1.267 + }
1.268 +
1.269 + // parent set for other p_loc_child
1.270 + child=container[p_loc].child;
1.271 + while( -1!=child ) {
1.272 + container[child].parent=loc;
1.273 + child=container[child].right_neighbor;
1.274 + }
1.275 +
1.276 + child=container[p_loc].child;
1.277 + container[p_loc].child=container[loc].child;
1.278 + if( child==loc )
1.279 + child=p_loc;
1.280 + container[loc].child=child;
1.281 +
1.282 + // left_neighb set for p_loc
1.283 + if( container[loc].child!=p_loc ) {
1.284 + while( container[child].right_neighbor!=loc )
1.285 + child=container[child].right_neighbor;
1.286 + container[child].right_neighbor=p_loc;
1.287 + }
1.288 +
1.289 + // left_neighb set for loc
1.290 + parent=container[p_loc].parent;
1.291 + if( -1!=parent ) child=container[parent].child;
1.292 + else child=head;
1.293 +
1.294 + if( child!=p_loc ) {
1.295 + while( container[child].right_neighbor!=p_loc )
1.296 + child=container[child].right_neighbor;
1.297 + container[child].right_neighbor=loc;
1.298 + }
1.299 +
1.300 + neighb=container[p_loc].right_neighbor;
1.301 + container[p_loc].right_neighbor=container[loc].right_neighbor;
1.302 + container[loc].right_neighbor=neighb;
1.303 +
1.304 + container[p_loc].parent=loc;
1.305 + container[loc].parent=parent;
1.306 +
1.307 + if( -1!=parent && container[parent].child==p_loc )
1.308 + container[parent].child=loc;
1.309 +
1.310 + /*if new parent will be the first root*/
1.311 + if( head==p_loc )
1.312 + head=loc;
1.313 +
1.314 + p_loc=container[loc].parent;
1.315 + }
1.316 + }
1.317 + if( comp(value,container[minimum].prio) ) {
1.318 + minimum=i;
1.319 + }
1.320 + }
1.321 +
1.322 + /// \brief Increases the priority of \c item to \c value.
1.323 + ///
1.324 + /// This method sets the priority of \c item to \c value. Though
1.325 + /// there is no precondition on the priority of \c item, this
1.326 + /// method should be used only if it is indeed necessary to increase
1.327 + /// (relative to \c Compare) the priority of \c item, because this
1.328 + /// method is inefficient.
1.329 + void increase (Item item, const Prio& value) {
1.330 + erase(item);
1.331 + push(item, value);
1.332 + }
1.333 +
1.334 +
1.335 + /// \brief Returns if \c item is in, has already been in, or has never
1.336 + /// been in the heap.
1.337 + ///
1.338 + /// This method returns PRE_HEAP if \c item has never been in the
1.339 + /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
1.340 + /// otherwise. In the latter case it is possible that \c item will
1.341 + /// get back to the heap again.
1.342 + State state(const Item &item) const {
1.343 + int i=iimap[item];
1.344 + if( i>=0 ) {
1.345 + if ( container[i].in ) i=0;
1.346 + else i=-2;
1.347 + }
1.348 + return State(i);
1.349 + }
1.350 +
1.351 + /// \brief Sets the state of the \c item in the heap.
1.352 + ///
1.353 + /// Sets the state of the \c item in the heap. It can be used to
1.354 + /// manually clear the heap when it is important to achive the
1.355 + /// better time complexity.
1.356 + /// \param i The item.
1.357 + /// \param st The state. It should not be \c IN_HEAP.
1.358 + void state(const Item& i, State st) {
1.359 + switch (st) {
1.360 + case POST_HEAP:
1.361 + case PRE_HEAP:
1.362 + if (state(i) == IN_HEAP) {
1.363 + erase(i);
1.364 + }
1.365 + iimap[i] = st;
1.366 + break;
1.367 + case IN_HEAP:
1.368 + break;
1.369 + }
1.370 + }
1.371 +
1.372 + private:
1.373 + int find_min() {
1.374 + int min_loc=-1, min_val;
1.375 + int x=head;
1.376 + if( x!=-1 ) {
1.377 + min_val=container[x].prio;
1.378 + min_loc=x;
1.379 + x=container[x].right_neighbor;
1.380 +
1.381 + while( x!=-1 ) {
1.382 + if( comp( container[x].prio,min_val ) ) {
1.383 + min_val=container[x].prio;
1.384 + min_loc=x;
1.385 + }
1.386 + x=container[x].right_neighbor;
1.387 + }
1.388 + }
1.389 + return min_loc;
1.390 + }
1.391 +
1.392 + void merge(int a) {
1.393 + interleave(a);
1.394 +
1.395 + int x=head;
1.396 + if( -1!=x ) {
1.397 + int x_prev=-1, x_next=container[x].right_neighbor;
1.398 + while( -1!=x_next ) {
1.399 + if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {
1.400 + x_prev=x;
1.401 + x=x_next;
1.402 + }
1.403 + else {
1.404 + if( comp(container[x].prio,container[x_next].prio) ) {
1.405 + container[x].right_neighbor=container[x_next].right_neighbor;
1.406 + fuse(x_next,x);
1.407 + }
1.408 + else {
1.409 + if( -1==x_prev ) { head=x_next; }
1.410 + else {
1.411 + container[x_prev].right_neighbor=x_next;
1.412 + }
1.413 + fuse(x,x_next);
1.414 + x=x_next;
1.415 + }
1.416 + }
1.417 + x_next=container[x].right_neighbor;
1.418 + }
1.419 + }
1.420 + }
1.421 +
1.422 + void interleave(int a) {
1.423 + int other=-1, head_other=-1;
1.424 +
1.425 + while( -1!=a || -1!=head ) {
1.426 + if( -1==a ) {
1.427 + if( -1==head_other ) {
1.428 + head_other=head;
1.429 + }
1.430 + else {
1.431 + container[other].right_neighbor=head;
1.432 + }
1.433 + head=-1;
1.434 + }
1.435 + else if( -1==head ) {
1.436 + if( -1==head_other ) {
1.437 + head_other=a;
1.438 + }
1.439 + else {
1.440 + container[other].right_neighbor=a;
1.441 + }
1.442 + a=-1;
1.443 + }
1.444 + else {
1.445 + if( container[a].degree<container[head].degree ) {
1.446 + if( -1==head_other ) {
1.447 + head_other=a;
1.448 + }
1.449 + else {
1.450 + container[other].right_neighbor=a;
1.451 + }
1.452 + other=a;
1.453 + a=container[a].right_neighbor;
1.454 + }
1.455 + else {
1.456 + if( -1==head_other ) {
1.457 + head_other=head;
1.458 + }
1.459 + else {
1.460 + container[other].right_neighbor=head;
1.461 + }
1.462 + other=head;
1.463 + head=container[head].right_neighbor;
1.464 + }
1.465 + }
1.466 + }
1.467 + head=head_other;
1.468 + }
1.469 +
1.470 + // Lacing a under b
1.471 + void fuse(int a, int b) {
1.472 + container[a].parent=b;
1.473 + container[a].right_neighbor=container[b].child;
1.474 + container[b].child=a;
1.475 +
1.476 + ++container[b].degree;
1.477 + }
1.478 +
1.479 + // It is invoked only if a has siblings.
1.480 + void unlace(int a) {
1.481 + int neighb=container[a].right_neighbor;
1.482 + int other=head;
1.483 +
1.484 + while( container[other].right_neighbor!=a )
1.485 + other=container[other].right_neighbor;
1.486 + container[other].right_neighbor=neighb;
1.487 + }
1.488 +
1.489 + private:
1.490 +
1.491 + class store {
1.492 + friend class BinomHeap;
1.493 +
1.494 + Item name;
1.495 + int parent;
1.496 + int right_neighbor;
1.497 + int child;
1.498 + int degree;
1.499 + bool in;
1.500 + Prio prio;
1.501 +
1.502 + store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
1.503 + };
1.504 + };
1.505 +
1.506 +} //namespace lemon
1.507 +
1.508 +#endif //LEMON_BINOM_HEAP_H
1.509 +