| Home | Libraries | People | FAQ | More

## 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 base_maker::node_type          node;
        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

1. 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

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

   Effects: constructs an empty priority queue.

   Complexity: Constant.

2.     binomial_heap(binomial_heap const & rhs);

   Effects: copy-constructs priority queue from rhs.

   Complexity: Linear.

3.     binomial_heap(binomial_heap && rhs);

   Effects: C++11-style move constructor.

   Complexity: Constant.

   Note: Only available, if BOOST_HAS_RVALUE_REFS is defined

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

5.     binomial_heap& operator=(binomial_heap const & rhs);

   Effects: Assigns priority queue from rhs.

   Complexity: Linear.

6.     binomial_heap& operator=(binomial_heap && rhs);

   Effects: C++11-style move assignment.

   Complexity: Constant.

   Note: Only available, if BOOST_HAS_RVALUE_REFS is defined

7.     ~binomial_heap(void);

### `binomial_heap` public member functions

1.     bool empty(void) const;

   Effects: Returns true, if the priority queue contains no elements.

   Complexity: Constant.

2.     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.

3.     size_type max_size(void) const;

   Effects: Returns the maximum number of elements the priority queue can contain.

   Complexity: Constant.

4.     void clear(void);

   Effects: Removes all elements from the priority queue.

   Complexity: Linear.

5.     allocator_type get_allocator(void) const;

   Effects: Returns allocator.

   Complexity: Constant.

6.     void swap(binomial_heap & rhs);

   Effects: Swaps two priority queues.

   Complexity: Constant.

7.     const_reference top(void) const;

   Effects: Returns a const_reference to the maximum element.

   Complexity: Constant.

8.     handle_type push(value_type const & v);

   Effects: Adds a new element to the priority queue. Returns handle to element

   Complexity: Logarithmic.

9.     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.

10.     void pop(void);

    Effects: Removes the top element from the priority queue.

    Complexity: Logarithmic.

11.     void update(handle_type handle, const_reference v);

    Effects: Assigns `v` to the element handled by `handle` & updates the priority queue.

    Complexity: Logarithmic.

12.     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!

13.     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

14.     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!

15.     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

16.     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!

17.     void merge(binomial_heap & rhs);

    Effects: Merge with priority queue rhs.

    Complexity: Logarithmic.

18.     iterator begin(void) const;

    Effects: Returns an iterator to the first element contained in the priority queue.

    Complexity: Constant.

19.     iterator end(void) const;

    Effects: Returns an iterator to the end of the priority queue.

    Complexity: Constant.

20.     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.

21.     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.

22.     void erase(handle_type handle);

    Effects: Removes the element handled by `handle` from the `priority_queue`.

    Complexity: Logarithmic.

23.     value_compare const & value_comp(void) const;

    Effect: Returns the value_compare object used by the priority queue

24.     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.

25.     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.

26.     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.

27.     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.

28.     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.

29.     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

1.     static handle_type s_handle_from_iterator(iterator const & it);

### `binomial_heap` private member functions

1.     void merge_and_clear_nodes(binomial_heap & rhs);

2.     void clone_forest(binomial_heap const & rhs);

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

4.     void siftdown(node_pointer n);

5.     void insert_node(node_list_iterator it, node_pointer n);

6.     node_pointer merge_trees(node_pointer node1, node_pointer node2);

7.     void update_top_element(void);

8.     void sorted_by_degree(void) const;

9.     void sanity_check(void);