Class template pairing

Class template pairing_heap

boost::heap::pairing_heap — pairing heap

Synopsis

// In header: <boost/heap/pairing_heap.hpp>

template<typename T,  Options> 
class pairing_heap {
public:
  // types
  typedef                                         ;      
  typedef         ;       
  typedef   ; 
  typedef     ;   
  typedef    ;  
  typedef         ;       
  typedef   ; 
  typedef           ;         
  typedef     ;   
  typedef          ;        
  typedef    ;  
  typedef  ;
  typedef       ;     

  // construct/copy/destruct
  ( = );
  ();
  ();
   ();
   ();
  ~();

  // public member functions
   () ;
   () ;
   () ;
   ();
   () ;
   ();
   () ;
   ();
  template< Args>  ();
   ();
   (, );
   ();
   (, );
   ();
   (, );
   ();
   ();
   () ;
   () ;
   () ;
   () ;
   ();
   () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;

  // public static functions
   ();

  // public data members
  static  constant_time_size;
  static  has_ordered_iterators;
  static  is_mergable;
  static  is_stable;
  static  has_reserve;
};

Description

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

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>
boost::heap::allocator<>, defaults to allocator<std::allocator<T> >
boost::heap::constant_time_size<>, defaults to constant_time_size<true>

`pairing_heap` public types

typedef ;

Note: The iterator does not traverse the priority queue in order of the priorities.

`pairing_heap` public construct/copy/destruct

```
( cmp = );
```
Effects: constructs an empty priority queue.

Complexity: Constant.
```
( rhs);
```
Effects: copy-constructs priority queue from rhs.

Complexity: Linear.
```
( rhs);
```
Effects: C++11-style move constructor.

Complexity: Constant.

Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
```
 ( rhs);
```
Effects: C++11-style move assignment.

Complexity: Constant.

Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
```
 ( rhs);
```
Effects: Assigns priority queue from rhs.

Complexity: Linear.
```
~();
```

`pairing_heap` public member functions

```
 () ;
```
Effects: Returns true, if the priority queue contains no elements.

Complexity: Constant.
```
 () ;
```
Effects: Returns the number of elements contained in the priority queue.

Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
```
 () ;
```
Effects: Returns the maximum number of elements the priority queue can contain.

Complexity: Constant.
```
 ();
```
Effects: Removes all elements from the priority queue.

Complexity: Linear.
```
 () ;
```
Effects: Returns allocator.

Complexity: Constant.
```
 ( rhs);
```
Effects: Swaps two priority queues.

Complexity: Constant.
```
 () ;
```
Effects: Returns a const_reference to the maximum element.

Complexity: Constant.
```
 ( v);
```
Effects: Adds a new element to the priority queue. Returns handle to element Complexity: 2**2*log(log(N)) (amortized).
```
template< 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).
```
 ();
```
Effects: Removes the top element from the priority queue.

Complexity: Logarithmic (amortized).
```
 ( handle,  v);
```
Effects: Assigns v to the element handled by handle & updates the priority queue. Complexity: 2**2*log(log(N)) (amortized).
```
 ( 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!
```
 ( handle,  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
```
 ( 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!
```
 ( handle,  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
```
 ( 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!
```
 ( handle);
```
Effects: Removes the element handled by handle from the priority_queue. Complexity: 2**2*log(log(N)) (amortized).
```
 () ;
```
Effects: Returns an iterator to the first element contained in the priority queue.

Complexity: Constant.
```
 () ;
```
Effects: Returns an iterator to the end of the priority queue.

Complexity: Constant.
```
 () ;
```
Effects: Returns an ordered iterator to the first element contained in the priority queue.

Note: Ordered iterators traverse the priority queue in heap order.
```
 () ;
```
Effects: Returns an ordered iterator to the first element contained in the priority queue.

Note: Ordered iterators traverse the priority queue in heap order.
```
 ( rhs);
```
Effects: Merge all elements from rhs into this Complexity: 2**2*log(log(N)) (amortized).
```
 () ;
```
Effect: Returns the value_compare object used by the priority queue
```
template<typename HeapType>  ( rhs) ;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType>  ( rhs) ;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType>  ( rhs) ;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType>  ( rhs) ;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType>  ( rhs) ;
```
Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType>  ( rhs) ;
```
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare object of both heaps must match.

`pairing_heap` public static functions

```
 ( it);
```