422 lines
18 KiB
Plaintext
422 lines
18 KiB
Plaintext
[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] |