123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422 |
- [library Boost.Heap
- [quickbook 1.4]
- [authors [Blechmann, Tim]]
- [copyright 2010-2011 Tim Blechmann]
- [category algorithms]
- [purpose
- heap data structures
- ]
- [id heap]
- [dirname heap]
- [license
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- [@http://www.boost.org/LICENSE_1_0.txt])
- ]
- ]
- [c++]
- [/ Links ]
- [def _heap_ [^boost.heap]]
- [/ unspecified stuff ]
- [def __unspecified_int__ /unspecified-int-type/]
- [def __unspecified__ /unspecified/]
- [def __unspecified_bool__ /unspecified-bool-type/]
- [section Introduction & Motivation]
- _heap_ is an implementation of priority queues. Priority queues are queue data structures, that order their elements by
- a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality.
- To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and
- different performance characteristics. Especially, it deals with additional aspects:
- * *Mutability*: The priority of heap elements can be modified.
- * *Iterators*: Heaps provide iterators to iterate all elements.
- * *Mergable*: While all heaps can be merged, some can be merged efficiently.
- * *Stability*: Heaps can be configured to be stable sorted.
- * *Comparison*: Heaps can be compared for equivalence.
- [endsect]
- [section:concepts Concepts & Interface]
- [section:basic Basic Priority Queue Interface]
- Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to
- the data structure, accessing the top element (the element with the highest priority), and removing the top element.
- [note _heap_ implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to
- the typical textbook design, which uses min-heaps.]
- [h5 Synopsis]
- template <typename T, class ...Options>
- class priority_queue
- {
- // types
- typedef T value_type;
- typedef ``/unspecified/`` size_type;
- typedef ``/unspecified/`` difference_type;
- typedef ``/unspecified/`` allocator_type;
- typedef ``/unspecified/`` value_compare;
- typedef ``/unspecified/`` reference;
- typedef ``/unspecified/`` const_reference;
- typedef ``/unspecified/`` pointer;
- typedef ``/unspecified/`` const_pointer;
- // construct/copy/destruct
- explicit priority_queue(value_compare const & = value_compare());
- priority_queue(priority_queue const &);
- priority_queue& operator=(priority_queue const &);
- priority_queue(priority_queue &&); // move semantics (C++11 only)
- priority_queue& operator=(priority_queue &&); // move semantics (C++11 only)
- // public member functions
- ``/unspecified/`` push(const_reference); // push new element to heap
- template<class... Args> void emplace(Args &&...); // push new element to heap, C++11 only
- const_reference top() const; // return top element
- void pop(); // remove top element
- void clear(); // clear heap
- size_type size() const; // number of elements
- bool empty() const; // priority queue is empty
- allocator_type get_allocator(void) const; // return allocator
- size_type max_size(void) const; // maximal possible size
- void reserve(size_type); // reserve space, only available if (has_reserve == true)
- // heap equivalence
- template<typename HeapType> bool operator==(HeapType const &) const;
- template<typename HeapType> bool operator!=(HeapType const &) const;
- // heap comparison
- template<typename HeapType> bool operator<(HeapType const &) const;
- template<typename HeapType> bool operator>(HeapType const &) const;
- template<typename HeapType> bool operator>=(HeapType const &) const;
- template<typename HeapType> bool operator<=(HeapType const &) const;
- // public data members
- static const bool constant_time_size; // size() has constant complexity
- static const bool has_ordered_iterators; // priority queue has ``[link heap.concepts.iterators ordered iterators]``
- static const bool is_mergable; // priority queue is efficiently ``[link heap.concepts.merge mergable]``
- static const bool is_stable; // priority queue has a ``[link heap.concepts.stability stable heap order]``
- static const bool has_reserve; // priority queue has a reserve() member
- };
- [h5 Example]
- [import ../examples/interface.cpp]
- [basic_interface]
- [endsect]
- [section:iterators Priority Queue Iterators]
- [h5 Synopsis]
- class iteratable_heap_interface
- {
- public:
- // types
- typedef ``/unspecified/`` iterator;
- typedef ``/unspecified/`` const_iterator;
- typedef ``/unspecified/`` ordered_iterator;
- // public member functions
- iterator begin(void) const;
- iterator end(void) const;
- ordered_iterator ordered_begin(void) const;
- ordered_iterator ordered_end(void) const;
- };
- Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means
- they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about
- modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface].
- Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate
- iterators, while all const member functions preserve the iterator validity.
- [note Some implementations require iterators, that contain a set of elements, that are *discovered*, but not *visited*. Therefore
- copying iterators can be inefficient and should be avoided.]
- [h5 Example]
- [iterator_interface]
- [section:ordered_iterators Ordered Iterators]
- Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements
- of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a
- heap in heap order has an amortized complexity of O(N*log(N)).
- [h5 Example]
- [ordered_iterator_interface]
- [endsect]
- [endsect]
- [section:comparing Comparing Priority Queues & Equivalence]
- The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two
- heaps element by element using =value_compare=.
- [note Depending on the heap type, this operation can be rather expensive, because both data structures need to be traversed in
- heap order. On heaps without ordered iterators, the heap needs to be copied internally. The typical complexity is O(n log(n)).]
- [endsect]
- [section:merge Merging Priority Queues]
- [h3 Mergable Priority Queues]
- [h5 Synopsis]
- class mergable_heap_interface
- {
- public:
- // public member functions
- void merge(mergable_heap_interface &);
- };
- _heap_ has a concept of a Mergable Priority Queue. A mergable priority queue can efficiently be merged with a different instance
- of the same type.
- [h5 Example]
- [merge_interface]
- [h3 Heap Merge Algorithms]
- _heap_ provides a =heap_merge()= algorithm that is can be used to merge different kinds of heaps. Using this algorithm, all _heap_
- data structures can be merged, although some cannot be merged efficiently.
- [h5 Example]
- [heap_merge_algorithm]
- [endsect]
- [section:mutability Mutability]
- Some priority queues of _heap_ are mutable, that means the priority of their elements can be changed. To achieve mutability,
- _heap_ introduces the concept of *handles*, which can be used to access the internal nodes of the priority queue in order to
- change its value and to restore the heap order.
- [h5 Synopsis]
- class mutable_heap_interface
- {
- public:
- typedef ``/unspecified/`` iterator;
- struct handle_type
- {
- value_type & operator*() const;
- };
- static handle_type s_iterator_to_handle(iterator const &);
- // priority queue interface
- handle_type push(T const & v);
- // update element via assignment and fix heap
- void update(handle_type const & handle, value_type const & v);
- void increase(handle_type const & handle, value_type const & v);
- void decrease(handle_type const & handle, value_type const & v);
- // fix heap after element has been changed via the handle
- void update(handle_type const & handle);
- void increase(handle_type const & handle);
- void decrease(handle_type const & handle);
- };
- [warning Incorrect use of =increase= or =decrease= may corrupt the priority queue data structure. If unsure use =update= can be
- used at the cost of efficiency.]
- [h5 Example]
- [mutable_interface]
- Note that handles can be stored inside the =value_type=:
- [mutable_interface_handle_in_value]
- [h3 The Fixup Interface]
- There are two different APIs to support mutability. The first family of functions provides update functionality by changing
- the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after
- an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue
- elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up
- immediately after the priority of the element has been changed.
- Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient
- than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right
- direction.
- [h5 Example]
- [mutable_fixup_interface]
- Iterators can be converted to handles using the static member function =s_handle_from_iterator=. However most implementations of
- =update= invalidate all iterators. The most notable exception is the [classref boost::heap::fibonacci_heap fibonacci heap],
- providing a lazy update function, that just invalidates the iterators, that are related to this handle.
- [warning After changing the priority via a handle, the heap needs to be fixed by calling one of the update functions. Otherwise the
- priority queue structure may be corrupted!]
- [endsect]
- [section:stability Stability]
- A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as
- they are inserted. The data structures provided by _heap_, can be configured to be stable at compile time using the
- [classref boost::heap::stable] policy. Two notions of stability are supported. If a heap is configured with *no stability*,
- the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by
- their insertion time.
- Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node.
- The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be
- configured to use a different type using the [classref boost::heap::stability_counter_type] template argument.
- [warning The stability counter is prone to integer overflows. If an overflow occurs during a =push()= call, the operation
- will fail and an exception is thrown. Later =push()= call will succeed, but the stable heap order will be compromised. However an
- integer overflow at 64bit is very unlikely: if an application would issue one =push()= operation per microsecond, the value will
- overflow in more than 500000 years.]
- [endsect]
- [endsect]
- [section:data_structures Data Structures]
- _heap_ provides the following data structures:
- [variablelist
- [[[classref boost::heap::priority_queue]]
- [
- The [classref boost::heap::priority_queue priority_queue] class is a wrapper to the stl heap functions. It implements
- a heap as container adaptor ontop of a =std::vector= and is immutable.
- ]
- ]
- [[[classref boost::heap::d_ary_heap]]
- [
- [@http://en.wikipedia.org/wiki/D-ary_heap D-ary heaps] are a generalization of binary heap with each non-leaf node
- having N children. For a low arity, the height of the heap is larger, but the number of comparisons to find the largest
- child node is bigger. D-ary heaps are implemented as container adaptors based on a =std::vector=.
- The data structure can be configured as mutable. This is achieved by storing the values inside a std::list.
- ]
- ]
- [[[classref boost::heap::binomial_heap]]
- [
- [@http://en.wikipedia.org/wiki/Binomial_heap Binomial heaps] are node-base heaps, that are implemented as a set of
- binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n).
- In contrast to d-ary heaps, binomial heaps can also be merged in O(log n).
- ]
- ]
- [[[classref boost::heap::fibonacci_heap]]
- [
- [@http://en.wikipedia.org/wiki/Fibonacci_heap Fibonacci heaps] are node-base heaps, that are implemented as a forest of
- heap-ordered trees. They provide better amortized performance than binomial heaps. Except =pop()= and =erase()=, the most
- important heap operations have constant amortized complexity.
- ]
- ]
- [[[classref boost::heap::pairing_heap]]
- [
- [@http://en.wikipedia.org/wiki/Pairing_heap Pairing heaps] are self-adjusting node-based heaps. Although design and
- implementation are rather simple, the complexity analysis is yet unsolved. For details, consult:
- Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183
- ]
- ]
- [[[classref boost::heap::skew_heap]]
- [
- [@http://en.wikipedia.org/wiki/Skew_heap Skew heaps] are self-adjusting node-based heaps. Although there are no
- constraints for the tree structure, all heap operations can be performed in O(log n).
- ]
- ]
- ]
- [table Comparison of amortized complexity
- [[] [[^top()]] [[^push()]] [[^pop()]] [[^update()]] [[^increase()]] [[^decrease()]] [[^erase()]] [[^merge_and_clear()]]]
- [[[classref boost::heap::priority_queue]] [[^O(1)]] [O(log(N))] [O(log(N))] [n/a] [n/a] [n/a] [n/a] [O((N+M)*log(N+M))]]
- [[[classref boost::heap::d_ary_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O((N+M)*log(N+M))]]
- [[[classref boost::heap::binomial_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]]
- [[[classref boost::heap::fibonacci_heap]] [[^O(1)]] [O(1)] [O(log(N))] [O(log(N))
- [footnote The fibonacci a [^update_lazy()] method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest]
- ] [O(1)] [O(log(N))] [O(log(N))] [O(1)]]
- [[[classref boost::heap::pairing_heap]] [[^O(1)]] [O(2**2*log(log(N)))] [O(log(N))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))]]
- [[[classref boost::heap::skew_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]]
- ]
- [section Data Structure Configuration]
- The data structures can be configured with [@boost:/libs/parameter/doc/html/index.html Boost.Parameter]-style templates.
- [variablelist
- [[[classref boost::heap::compare]]
- [Predicate for defining the heap order, optional
- (defaults to =boost::heap::compare<std::less<T> >=)]
- ]
- [[[classref boost::heap::allocator]]
- [Allocator for internal memory management, optional
- (defaults to =boost::heap::allocator<std::allocator<T> >=)]
- ]
- [[[classref boost::heap::stable]]
- [Configures the heap to use a [link heap.concepts.stability stable heap order], optional (defaults to =boost::heap::stable<false>=).
- ]
- ]
- [[[classref boost::heap::mutable_]]
- [Configures the heap to be mutable. [classref boost::heap::d_ary_heap] and [classref boost::heap::skew_heap] have to be configured
- with this policy to enable the [link heap.concepts.mutability mutability interface].
- ]
- ]
- [[[classref boost::heap::stability_counter_type]]
- [Configures the integer type used for the stability counter, optional (defaults to =boost::heap::stability_counter_type<boost::uintmax_t>=).
- For more details, consult the [link heap.concepts.stability Stability] section.
- ]
- ]
- [[[classref boost::heap::constant_time_size]]
- [Specifies, whether =size()= should have linear or constant complexity. This argument is only available for node-based
- heap data structures and if available, it is optional (defaults to =boost::heap::constant_time_size<true>=)]
- ]
- [[[classref boost::heap::arity]]
- [Specifies the arity of a d-ary heap. For details, please consult the class reference of [classref boost::heap::d_ary_heap]]
- ]
- [[[classref boost::heap::store_parent_pointer]]
- [Store the parent pointer in the heap nodes. This policy is only available in the [classref boost::heap::skew_heap].
- ]
- ]
- ]
- [endsect]
- [endsect]
- [xinclude autodoc.xml]
- [section Acknowledgements]
- [variablelist
- [[Google Inc.]
- [For sponsoring the development of this library during the Summer of Code 2010]
- ]
- [[Hartmut Kaiser]
- [For mentoring the Summer of Code project]
- ]
- ]
- [endsect]
|