binomial heap More...
#include <binomial_heap.hpp>
Public Types | |
typedef T | value_type |
typedef implementation_defined::size_type | size_type |
typedef implementation_defined::difference_type | difference_type |
typedef implementation_defined::value_compare | value_compare |
typedef implementation_defined::allocator_type | allocator_type |
typedef implementation_defined::reference | reference |
typedef implementation_defined::const_reference | const_reference |
typedef implementation_defined::pointer | pointer |
typedef implementation_defined::const_pointer | const_pointer |
typedef implementation_defined::iterator | iterator |
Note: The iterator does not traverse the priority queue in order of the priorities. More... | |
typedef implementation_defined::const_iterator | const_iterator |
typedef implementation_defined::ordered_iterator | ordered_iterator |
typedef implementation_defined::handle_type | handle_type |
Public Member Functions | |
binomial_heap (value_compare const &cmp=value_compare()) | |
Effects: constructs an empty priority queue. More... | |
binomial_heap (binomial_heap const &rhs) | |
Effects: copy-constructs priority queue from rhs. More... | |
binomial_heap & | operator= (binomial_heap const &rhs) |
Effects: Assigns priority queue from rhs. More... | |
binomial_heap (binomial_heap &&rhs) | |
Effects: C++11-style move constructor. More... | |
binomial_heap & | operator= (binomial_heap &&rhs) |
Effects: C++11-style move assignment. More... | |
~binomial_heap (void) | |
bool | empty (void) const |
Effects: Returns true, if the priority queue contains no elements. More... | |
size_type | size (void) const |
Effects: Returns the number of elements contained in the priority queue. More... | |
size_type | max_size (void) const |
Effects: Returns the maximum number of elements the priority queue can contain. More... | |
void | clear (void) |
Effects: Removes all elements from the priority queue. More... | |
allocator_type | get_allocator (void) const |
Effects: Returns allocator. More... | |
void | swap (binomial_heap &rhs) |
Effects: Swaps two priority queues. More... | |
const_reference | top (void) const |
Effects: Returns a const_reference to the maximum element. More... | |
handle_type | push (value_type const &v) |
Effects: Adds a new element to the priority queue. More... | |
template<class... Args> | |
handle_type | emplace (Args &&...args) |
Effects: Adds a new element to the priority queue. More... | |
void | pop (void) |
Effects: Removes the top element from the priority queue. More... | |
void | update (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | update (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | increase (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | increase (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | decrease (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | decrease (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | merge (binomial_heap &rhs) |
Effects: Merge with priority queue rhs. More... | |
iterator | begin (void) const |
Effects: Returns an iterator to the first element contained in the priority queue. More... | |
iterator | end (void) const |
Effects: Returns an iterator to the end of the priority queue. More... | |
ordered_iterator | ordered_begin (void) const |
Effects: Returns an ordered iterator to the first element contained in the priority queue. More... | |
ordered_iterator | ordered_end (void) const |
Effects: Returns an ordered iterator to the end of the priority queue. More... | |
void | erase (handle_type handle) |
Effects: Removes the element handled by handle from the priority_queue. More... | |
value_compare const & | value_comp (void) const |
Effect: Returns the value_compare object used by the priority queue More... | |
template<typename HeapType > | |
bool | operator< (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator> (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator>= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator<= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator== (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are equivalent. More... | |
template<typename HeapType > | |
bool | operator!= (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are not equivalent. More... | |
Static Public Member Functions | |
static handle_type | s_handle_from_iterator (iterator const &it) |
Static Public Attributes | |
static const bool | constant_time_size = super_t::constant_time_size |
static const bool | has_ordered_iterators = true |
static const bool | is_mergable = true |
static const bool | is_stable = detail::extract_stable<bound_args>::value |
static const bool | has_reserve = false |
Friends | |
template<typename Heap1 , typename Heap2 > | |
struct | heap_merge_emulate |
binomial heap
The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.
The container supports the following options:
boost::heap::stable<>
, defaults to stable<false>
boost::heap::compare<>
, defaults to compare<std::less<T>
>boost::heap::allocator<>
, defaults to allocator<std::allocator<T>
>boost::heap::constant_time_size<>
, defaults to constant_time_size<true>
boost::heap::stability_counter_type<>
, defaults to stability_counter_type<boost::uintmax_t>
typedef implementation_defined::allocator_type boost::heap::binomial_heap< T, A0, A1, A2, A3 >::allocator_type |
typedef implementation_defined::const_iterator boost::heap::binomial_heap< T, A0, A1, A2, A3 >::const_iterator |
typedef implementation_defined::const_pointer boost::heap::binomial_heap< T, A0, A1, A2, A3 >::const_pointer |
typedef implementation_defined::const_reference boost::heap::binomial_heap< T, A0, A1, A2, A3 >::const_reference |
typedef implementation_defined::difference_type boost::heap::binomial_heap< T, A0, A1, A2, A3 >::difference_type |
typedef implementation_defined::handle_type boost::heap::binomial_heap< T, A0, A1, A2, A3 >::handle_type |
typedef implementation_defined::iterator boost::heap::binomial_heap< T, A0, A1, A2, A3 >::iterator |
Note: The iterator does not traverse the priority queue in order of the priorities.
typedef implementation_defined::ordered_iterator boost::heap::binomial_heap< T, A0, A1, A2, A3 >::ordered_iterator |
typedef implementation_defined::pointer boost::heap::binomial_heap< T, A0, A1, A2, A3 >::pointer |
typedef implementation_defined::reference boost::heap::binomial_heap< T, A0, A1, A2, A3 >::reference |
typedef implementation_defined::size_type boost::heap::binomial_heap< T, A0, A1, A2, A3 >::size_type |
typedef implementation_defined::value_compare boost::heap::binomial_heap< T, A0, A1, A2, A3 >::value_compare |
typedef T boost::heap::binomial_heap< T, A0, A1, A2, A3 >::value_type |
|
inlineexplicit |
Effects: constructs an empty priority queue.
Complexity: Constant.
|
inline |
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty().
|
inline |
Effects: C++11-style move constructor.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
|
inline |
|
inline |
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
|
inline |
Effects: Removes all elements from the priority queue.
Complexity: Linear.
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator=(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::~binomial_heap().
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Note: The new value is expected to be less than the current one
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::update().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
References boost::n.
|
inline |
Effects: Adds a new element to the priority queue.
The element is directly constructed in-place. Returns handle to element.
Complexity: Logarithmic.
References boost::python::args(), boost::numeric::ublas::increment(), and boost::n.
|
inline |
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::binomial_heap(), boost::heap::binomial_heap< T, A0, A1, A2, A3 >::merge(), boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator=(), boost::heap::binomial_heap< T, A0, A1, A2, A3 >::pop(), boost::heap::binomial_heap< T, A0, A1, A2, A3 >::size(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::top().
|
inline |
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
|
inline |
Effects: Removes the element handled by handle
from the priority_queue.
Complexity: Logarithmic.
References boost::n, and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::pop().
|
inline |
Effects: Returns allocator.
Complexity: Constant.
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Note: The new value is expected to be greater than the current one
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::update().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
References boost::n.
|
inline |
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
|
inline |
Effects: Merge with priority queue rhs.
Complexity: Logarithmic.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty(), boost::accumulators::extract::max, and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::swap().
|
inline |
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator>=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator>().
|
inline |
Effects: Assigns priority queue from rhs.
Complexity: Linear.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::clear(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty().
|
inline |
Effects: C++11-style move assignment.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::clear(), boost::fusion::move(), and boost::heap::detail::make_binomial_heap_base< T, Parspec >::type::operator=().
|
inline |
Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator<=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::operator<().
|
inline |
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Returns an ordered iterator to the end of the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic.
References BOOST_ASSERT, boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty(), boost::heap::binomial_heap< T, A0, A1, A2, A3 >::swap(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::value_comp().
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::erase().
|
inline |
Effects: Adds a new element to the priority queue.
Returns handle to element
Complexity: Logarithmic.
References boost::numeric::ublas::increment(), and boost::n.
|
inlinestatic |
References boost::python::ptr().
|
inline |
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty().
|
inline |
Effects: Swaps two priority queues.
Complexity: Constant.
References boost::swap.
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::merge(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::pop().
|
inline |
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
References BOOST_ASSERT, and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::empty().
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::decrease(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::increase().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
References boost::heap::binomial_heap< T, A0, A1, A2, A3 >::decrease(), and boost::heap::binomial_heap< T, A0, A1, A2, A3 >::increase().
|
inline |
Effect: Returns the value_compare object used by the priority queue
Referenced by boost::heap::binomial_heap< T, A0, A1, A2, A3 >::pop().
|
friend |
|
static |
|
static |
|
static |
|
static |
|
static |