Class template binomial

Class template binomial_heap

boost::heap::binomial_heap — binomial heap

Synopsis

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

template<typename T, class... Options> 
class binomial_heap {
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;        
  typedef implementation_defined::const_iterator   const_iterator;  
  typedef implementation_defined::ordered_iterator ordered_iterator;
  typedef implementation_defined::handle_type      handle_type;     

  // member classes/structs/unions
  template<typename T, typename A0 = boost::parameter::void_, 
           typename A1 = boost::parameter::void_, 
           typename A2 = boost::parameter::void_, 
           typename A3 = boost::parameter::void_> 
  struct force_inf {

    // public member functions
    template<typename X> bool operator()(X const &, X const &) const;
  };
  template<typename T, typename A0 = boost::parameter::void_, 
           typename A1 = boost::parameter::void_, 
           typename A2 = boost::parameter::void_, 
           typename A3 = boost::parameter::void_> 
  struct implementation_defined {
    // types
    typedef T                              value_type;              
    typedef unspecified                    size_type;               
    typedef unspecified                    reference;               
    typedef base_maker::compare_argument   value_compare;           
    typedef base_maker::allocator_type     allocator_type;          
    typedef allocator_type::pointer        node_pointer;            
    typedef allocator_type::const_pointer  const_node_pointer;      
    typedef unspecified                    handle_type;             
    typedef base_maker::node_type          node_type;               
    typedef unspecified                    node_list_type;          
    typedef node_list_type::iterator       node_list_iterator;      
    typedef node_list_type::const_iterator node_list_const_iterator;
    typedef unspecified                    value_extractor;         
    typedef unspecified                    iterator;                
    typedef iterator                       const_iterator;          
    typedef unspecified                    ordered_iterator;        
  };

  // construct/copy/destruct
  explicit binomial_heap(value_compare const & = value_compare());
  binomial_heap(binomial_heap const &);
  binomial_heap(binomial_heap &&);
  explicit binomial_heap(value_compare const &, node_list_type &, size_type);
  binomial_heap& operator=(binomial_heap const &);
  binomial_heap& operator=(binomial_heap &&);
  ~binomial_heap(void);

  // public member functions
  bool empty(void) const;
  size_type size(void) const;
  size_type max_size(void) const;
  void clear(void);
  allocator_type get_allocator(void) const;
  void swap(binomial_heap &);
  const_reference top(void) const;
  handle_type push(value_type const &);
  template<class... Args> handle_type emplace(Args &&...);
  void pop(void);
  void update(handle_type, const_reference);
  void update(handle_type);
  void increase(handle_type, const_reference);
  void increase(handle_type);
  void decrease(handle_type, const_reference);
  void decrease(handle_type);
  void merge(binomial_heap &);
  iterator begin(void) const;
  iterator end(void) const;
  ordered_iterator ordered_begin(void) const;
  ordered_iterator ordered_end(void) const;
  void erase(handle_type);
  value_compare const & value_comp(void) 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;
  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 static functions
  static handle_type s_handle_from_iterator(iterator const &);

  // private member functions
  void merge_and_clear_nodes(binomial_heap &);
  void clone_forest(binomial_heap const &);
  template<typename Compare> void siftup(node_pointer, Compare const &);
  void siftdown(node_pointer);
  void insert_node(node_list_iterator, node_pointer);
  node_pointer merge_trees(node_pointer, node_pointer);
  void update_top_element(void);
  void sorted_by_degree(void) const;
  void sanity_check(void);

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

Description

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>

`binomial_heap` public types

typedef implementation_defined::iterator iterator;

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

`binomial_heap` public construct/copy/destruct

explicit binomial_heap(value_compare const & cmp = value_compare());

Effects: constructs an empty priority queue.

Complexity: Constant.

```
binomial_heap(binomial_heap const & rhs);
```
Effects: copy-constructs priority queue from rhs.

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

Complexity: Constant.

Note: Only available, if BOOST_HAS_RVALUE_REFS is defined

explicit binomial_heap(value_compare const & cmp, node_list_type & child_list, 
                       size_type size);

```
binomial_heap& operator=(binomial_heap const & rhs);
```
Effects: Assigns priority queue from rhs.

Complexity: Linear.
```
binomial_heap& operator=(binomial_heap && rhs);
```
Effects: C++11-style move assignment.

Complexity: Constant.

Note: Only available, if BOOST_HAS_RVALUE_REFS is defined
```
~binomial_heap(void);
```

`binomial_heap` public member functions

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

Complexity: Constant.
```
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;
```
Effects: Returns the maximum number of elements the priority queue can contain.

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

Complexity: Linear.
```
allocator_type get_allocator(void) const;
```
Effects: Returns allocator.

Complexity: Constant.
```
void swap(binomial_heap & rhs);
```
Effects: Swaps two priority queues.

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

Complexity: Constant.
```
handle_type push(value_type const & v);
```
Effects: Adds a new element to the priority queue. Returns handle to element

Complexity: Logarithmic.
```
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: Logarithmic.
```
void pop(void);
```
Effects: Removes the top element from the priority queue.

Complexity: Logarithmic.
```
void update(handle_type handle, const_reference v);
```
Effects: Assigns v to the element handled by handle & updates the priority queue.

Complexity: Logarithmic.
```
void update(handle_type handle);
```
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!
```
void increase(handle_type handle, const_reference v);
```
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
```
void increase(handle_type handle);
```
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!
```
void decrease(handle_type handle, const_reference v);
```
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
```
void decrease(handle_type handle);
```
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!
```
void merge(binomial_heap & rhs);
```
Effects: Merge with priority queue rhs.

Complexity: Logarithmic.
```
iterator begin(void) const;
```
Effects: Returns an iterator to the first element contained in the priority queue.

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

Complexity: Constant.
```
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;
```
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 erase(handle_type handle);
```
Effects: Removes the element handled by handle from the priority_queue.

Complexity: Logarithmic.
```
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;
```
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;
```
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;
```
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;
```
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 not equivalent.

Requirement: the value_compare object of both heaps must match.

`binomial_heap` public static functions

static handle_type s_handle_from_iterator(iterator const & it);

`binomial_heap` private member functions

void merge_and_clear_nodes(binomial_heap & rhs);

void clone_forest(binomial_heap const & rhs);

template<typename Compare> void siftup(node_pointer n, Compare const & cmp);

```
void siftdown(node_pointer n);
```

void insert_node(node_list_iterator it, node_pointer n);

node_pointer merge_trees(node_pointer node1, node_pointer node2);

```
void update_top_element(void);
```
```
void sorted_by_degree(void) const;
```
```
void sanity_check(void);
```

Class template binomial_heap

Synopsis

Description

binomial_heap public types

binomial_heap public construct/copy/destruct

binomial_heap public member functions

binomial_heap public static functions

binomial_heap private member functions

`binomial_heap` public types

`binomial_heap` public construct/copy/destruct

`binomial_heap` public member functions

`binomial_heap` public static functions

`binomial_heap` private member functions