Pairing heaps are self-adjusting binary 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
+Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174-183
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::compare<>, defaults to compare<std::less<T> >
boost::heap::stable<>, defaults to stable<false>
boost::heap::stability_counter_type<>, defaults to stability_counter_type<boost::uintmax_t>
pairing_heap
public
construct/copy/destructexplicit pairing_heap(value_compare const & cmp = value_compare());+
explicit pairing_heap(value_compare const & cmp = value_compare());
Effects: constructs an empty priority queue.
Complexity: Constant.
--
pairing_heap(pairing_heap const & rhs);+
pairing_heap(pairing_heap const & rhs);
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
--
pairing_heap(pairing_heap && rhs);+
pairing_heap(pairing_heap && rhs);
Effects: C++11-style move constructor.
Complexity: Constant.
-Note: Only available, if BOOST_HAS_RVALUE_REFS is defined
--
+Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
pairing_heap& operator=(pairing_heap && rhs);+
pairing_heap & operator=(pairing_heap && rhs);
Effects: C++11-style move assignment.
Complexity: Constant.
-Note: Only available, if BOOST_HAS_RVALUE_REFS is defined
--
+Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
pairing_heap& operator=(pairing_heap const & rhs);+
pairing_heap & operator=(pairing_heap const & rhs);
Effects: Assigns priority queue from rhs.
Complexity: Linear.
--
~pairing_heap(void);
~pairing_heap(void);
pairing_heap public member functionspairing_heap public member functionsbool empty(void) const;+
bool empty(void) const;
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
--
size_type size(void) const;+
size_type size(void) const;
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
--
size_type max_size(void) const;+
size_type max_size(void) const;
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
--
void clear(void);+
void clear(void);
Effects: Removes all elements from the priority queue.
Complexity: Linear.
--
allocator_type get_allocator(void) const;+
allocator_type get_allocator(void) const;
Effects: Returns allocator.
Complexity: Constant.
--
void swap(pairing_heap & rhs);+
void swap(pairing_heap & rhs);
Effects: Swaps two priority queues.
Complexity: Constant.
--
const_reference top(void) const;+
const_reference top(void) const;
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
--
handle_type push(value_type const & v);+
handle_type push(value_type const & v);
Effects: Adds a new element to the priority queue. Returns handle to element
Complexity: 2**2*log(log(N)) (amortized).
template<class... Args> handle_type emplace(Args &&... args);+
template<class... Args> handle_type emplace(Args &&... args);
Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
Complexity: 2**2*log(log(N)) (amortized).
void pop(void);+
void pop(void);
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic (amortized).
void update(handle_type handle, const_reference v);+
void update(handle_type handle, const_reference v);
Effects: Assigns v to the element handled by handle & updates the priority queue.
Complexity: 2**2*log(log(N)) (amortized).
void update(handle_type handle);+
void update(handle_type handle);
Effects: Updates the heap after the element handled by handle has been changed.
Complexity: 2**2*log(log(N)) (amortized).
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
void increase(handle_type handle, const_reference v);+
void increase(handle_type handle, const_reference v);
Effects: Assigns v to the element handled by handle & updates the priority queue.
Complexity: 2**2*log(log(N)) (amortized).
Note: The new value is expected to be greater than the current one
void increase(handle_type handle);+
void increase(handle_type handle);
Effects: Updates the heap after the element handled by handle has been changed.
Complexity: 2**2*log(log(N)) (amortized).
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
void decrease(handle_type handle, const_reference v);+
void decrease(handle_type handle, const_reference v);
Effects: Assigns v to the element handled by handle & updates the priority queue.
Complexity: 2**2*log(log(N)) (amortized).
Note: The new value is expected to be less than the current one
void decrease(handle_type handle);+
void decrease(handle_type handle);
Effects: Updates the heap after the element handled by handle has been changed.
Complexity: 2**2*log(log(N)) (amortized).
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!
void erase(handle_type handle);+
void erase(handle_type handle);
Effects: Removes the element handled by handle from the priority_queue.
Complexity: 2**2*log(log(N)) (amortized).
iterator begin(void) const;+
iterator begin(void) const;
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
--
iterator end(void) const;+
iterator end(void) const;
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
--
ordered_iterator ordered_begin(void) const;+
ordered_iterator ordered_begin(void) const;
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
--
ordered_iterator ordered_end(void) const;+
ordered_iterator ordered_end(void) const;
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
--
void merge(pairing_heap & rhs);+
void merge(pairing_heap & rhs);
Effects: Merge all elements from rhs into this
Complexity: 2**2*log(log(N)) (amortized).
value_compare const & value_comp(void) const;+
value_compare const & value_comp(void) const;
Effect: Returns the value_compare object used by the priority queue
--
template<typename HeapType> bool operator<(HeapType const & rhs) const;+
template<typename HeapType> bool operator<(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
-
template<typename HeapType> bool operator>(HeapType const & rhs) const;+
template<typename HeapType> bool operator>(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
-
template<typename HeapType> bool operator>=(HeapType const & rhs) const;+
template<typename HeapType> bool operator>=(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
-
template<typename HeapType> bool operator<=(HeapType const & rhs) const;+
template<typename HeapType> bool operator<=(HeapType const & rhs) const;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare object of both heaps must match.
-
template<typename HeapType> bool operator==(HeapType const & rhs) const;-
Equivalent comparison Returns: True, if both heap data structures are equivalent.
-Requirement: the value_compare object of both heaps must match.
-
+template<typename HeapType> bool operator==(HeapType const & rhs) const;Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare object of both heaps must match.
template<typename HeapType> bool operator!=(HeapType const & rhs) const;-
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
-Requirement: the value_compare object of both heaps must match.
-
+template<typename HeapType> bool operator!=(HeapType const & rhs) const;Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare object of both heaps must match.