1 // boost heap: binomial heap
3 // Copyright (C) 2010 Tim Blechmann
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 #ifndef BOOST_HEAP_BINOMIAL_HEAP_HPP
10 #define BOOST_HEAP_BINOMIAL_HEAP_HPP
16 #include <boost/assert.hpp>
18 #include <boost/heap/detail/heap_comparison.hpp>
19 #include <boost/heap/detail/heap_node.hpp>
20 #include <boost/heap/detail/stable_heap.hpp>
21 #include <boost/heap/detail/tree_iterator.hpp>
23 #ifdef BOOST_HAS_PRAGMA_ONCE
27 #ifndef BOOST_DOXYGEN_INVOKED
28 #ifdef BOOST_HEAP_SANITYCHECKS
29 #define BOOST_HEAP_ASSERT BOOST_ASSERT
31 #define BOOST_HEAP_ASSERT(expression)
39 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
40 boost::parameter::optional<tag::compare>,
41 boost::parameter::optional<tag::stable>,
42 boost::parameter::optional<tag::constant_time_size>,
43 boost::parameter::optional<tag::stability_counter_type>
44 > binomial_heap_signature;
46 template <typename T, typename Parspec>
47 struct make_binomial_heap_base
49 static const bool constant_time_size = parameter::binding<Parspec,
50 tag::constant_time_size,
53 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::type base_type;
54 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::allocator_argument allocator_argument;
55 typedef typename detail::make_heap_base<T, Parspec, constant_time_size>::compare_argument compare_argument;
57 typedef parent_pointing_heap_node<typename base_type::internal_type> node_type;
59 typedef typename allocator_argument::template rebind<node_type>::other allocator_type;
65 type(compare_argument const & arg):
69 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
70 type(type const & rhs):
71 base_type(rhs), allocator_type(rhs)
75 base_type(std::move(static_cast<base_type&>(rhs))),
76 allocator_type(std::move(static_cast<allocator_type&>(rhs)))
79 type & operator=(type && rhs)
81 base_type::operator=(std::move(static_cast<base_type&>(rhs)));
82 allocator_type::operator=(std::move(static_cast<allocator_type&>(rhs)));
86 type & operator=(type const & rhs)
88 base_type::operator=(static_cast<base_type const &>(rhs));
89 allocator_type::operator=(static_cast<allocator_type const &>(rhs));
99 * \class binomial_heap
100 * \brief binomial heap
102 * The template parameter T is the type to be managed by the container.
103 * The user can specify additional options and if no options are provided default options are used.
105 * The container supports the following options:
106 * - \c boost::heap::stable<>, defaults to \c stable<false>
107 * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
108 * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
109 * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
110 * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
113 #ifdef BOOST_DOXYGEN_INVOKED
114 template<class T, class ...Options>
116 template <typename T,
117 class A0 = boost::parameter::void_,
118 class A1 = boost::parameter::void_,
119 class A2 = boost::parameter::void_,
120 class A3 = boost::parameter::void_
124 private detail::make_binomial_heap_base<T,
125 typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type
128 typedef typename detail::binomial_heap_signature::bind<A0, A1, A2, A3>::type bound_args;
129 typedef detail::make_binomial_heap_base<T, bound_args> base_maker;
130 typedef typename base_maker::type super_t;
132 typedef typename super_t::internal_type internal_type;
133 typedef typename super_t::size_holder_type size_holder;
134 typedef typename super_t::stability_counter_type stability_counter_type;
135 typedef typename base_maker::allocator_argument allocator_argument;
137 template <typename Heap1, typename Heap2>
138 friend struct heap_merge_emulate;
141 static const bool constant_time_size = super_t::constant_time_size;
142 static const bool has_ordered_iterators = true;
143 static const bool is_mergable = true;
144 static const bool is_stable = detail::extract_stable<bound_args>::value;
145 static const bool has_reserve = false;
148 #ifndef BOOST_DOXYGEN_INVOKED
149 struct implementation_defined:
150 detail::extract_allocator_types<typename base_maker::allocator_argument>
152 typedef T value_type;
153 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::size_type size_type;
154 typedef typename detail::extract_allocator_types<typename base_maker::allocator_argument>::reference reference;
156 typedef typename base_maker::compare_argument value_compare;
157 typedef typename base_maker::allocator_type allocator_type;
158 typedef typename base_maker::node_type node;
160 typedef typename allocator_type::pointer node_pointer;
161 typedef typename allocator_type::const_pointer const_node_pointer;
163 typedef detail::node_handle<node_pointer, super_t, reference> handle_type;
165 typedef typename base_maker::node_type node_type;
167 typedef boost::intrusive::list<detail::heap_node_base<false>,
168 boost::intrusive::constant_time_size<true>
171 typedef typename node_list_type::iterator node_list_iterator;
172 typedef typename node_list_type::const_iterator node_list_const_iterator;
173 typedef detail::value_extractor<value_type, internal_type, super_t> value_extractor;
175 typedef detail::recursive_tree_iterator<node_type,
176 node_list_const_iterator,
179 detail::list_iterator_converter<node_type, node_list_type>
181 typedef iterator const_iterator;
183 typedef detail::tree_iterator<node_type,
187 detail::list_iterator_converter<node_type, node_list_type>,
196 typedef T value_type;
198 typedef typename implementation_defined::size_type size_type;
199 typedef typename implementation_defined::difference_type difference_type;
200 typedef typename implementation_defined::value_compare value_compare;
201 typedef typename implementation_defined::allocator_type allocator_type;
202 typedef typename implementation_defined::reference reference;
203 typedef typename implementation_defined::const_reference const_reference;
204 typedef typename implementation_defined::pointer pointer;
205 typedef typename implementation_defined::const_pointer const_pointer;
206 /// \copydoc boost::heap::priority_queue::iterator
207 typedef typename implementation_defined::iterator iterator;
208 typedef typename implementation_defined::const_iterator const_iterator;
209 typedef typename implementation_defined::ordered_iterator ordered_iterator;
211 typedef typename implementation_defined::handle_type handle_type;
214 typedef typename implementation_defined::node_type node_type;
215 typedef typename implementation_defined::node_list_type node_list_type;
216 typedef typename implementation_defined::node_pointer node_pointer;
217 typedef typename implementation_defined::const_node_pointer const_node_pointer;
218 typedef typename implementation_defined::node_list_iterator node_list_iterator;
219 typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
221 typedef typename super_t::internal_compare internal_compare;
224 /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
225 explicit binomial_heap(value_compare const & cmp = value_compare()):
226 super_t(cmp), top_element(0)
229 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
230 binomial_heap(binomial_heap const & rhs):
231 super_t(rhs), top_element(0)
237 size_holder::set_size(rhs.get_size());
240 /// \copydoc boost::heap::priority_queue::operator=(priority_queue const &)
241 binomial_heap & operator=(binomial_heap const & rhs)
244 size_holder::set_size(rhs.get_size());
245 static_cast<super_t&>(*this) = rhs;
254 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
255 /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
256 binomial_heap(binomial_heap && rhs):
257 super_t(std::move(rhs)), top_element(rhs.top_element)
259 trees.splice(trees.begin(), rhs.trees);
260 rhs.top_element = NULL;
263 /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
264 binomial_heap & operator=(binomial_heap && rhs)
267 super_t::operator=(std::move(rhs));
268 trees.splice(trees.begin(), rhs.trees);
269 top_element = rhs.top_element;
270 rhs.top_element = NULL;
280 /// \copydoc boost::heap::priority_queue::empty
281 bool empty(void) const
283 return top_element == NULL;
287 * \b Effects: Returns the number of elements contained in the priority queue.
289 * \b Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.
292 size_type size(void) const
294 if (constant_time_size)
295 return size_holder::get_size();
300 return detail::count_list_nodes<node_type, node_list_type>(trees);
303 /// \copydoc boost::heap::priority_queue::max_size
304 size_type max_size(void) const
306 return allocator_type::max_size();
309 /// \copydoc boost::heap::priority_queue::clear
312 typedef detail::node_disposer<node_type, typename node_list_type::value_type, allocator_type> disposer;
313 trees.clear_and_dispose(disposer(*this));
315 size_holder::set_size(0);
319 /// \copydoc boost::heap::priority_queue::get_allocator
320 allocator_type get_allocator(void) const
325 /// \copydoc boost::heap::priority_queue::swap
326 void swap(binomial_heap & rhs)
329 std::swap(top_element, rhs.top_element);
330 trees.swap(rhs.trees);
333 /// \copydoc boost::heap::priority_queue::top
334 const_reference top(void) const
336 BOOST_ASSERT(!empty());
338 return super_t::get_value(top_element->value);
342 * \b Effects: Adds a new element to the priority queue. Returns handle to element
344 * \b Complexity: Logarithmic.
347 handle_type push(value_type const & v)
349 node_pointer n = allocator_type::allocate(1);
350 new(n) node_type(super_t::make_node(v));
352 insert_node(trees.begin(), n);
354 if (!top_element || super_t::operator()(top_element->value, n->value))
357 size_holder::increment();
359 return handle_type(n);
362 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
364 * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns handle to element.
366 * \b Complexity: Logarithmic.
369 template <class... Args>
370 handle_type emplace(Args&&... args)
372 node_pointer n = allocator_type::allocate(1);
373 new(n) node_type(super_t::make_node(std::forward<Args>(args)...));
375 insert_node(trees.begin(), n);
377 if (!top_element || super_t::operator()(top_element->value, n->value))
380 size_holder::increment();
382 return handle_type(n);
387 * \b Effects: Removes the top element from the priority queue.
389 * \b Complexity: Logarithmic.
394 BOOST_ASSERT(!empty());
396 node_pointer element = top_element;
398 trees.erase(node_list_type::s_iterator_to(*element));
399 size_holder::decrement();
401 if (element->child_count()) {
402 size_type sz = (1 << element->child_count()) - 1;
404 binomial_heap children(value_comp(), element->children, sz);
406 stability_counter_type stability_count = super_t::get_stability_count();
407 size_t size = constant_time_size ? size_holder::get_size()
410 super_t::set_stability_count(stability_count);
412 if (constant_time_size)
413 size_holder::set_size( size );
415 merge_and_clear_nodes(children);
422 update_top_element();
424 element->~node_type();
425 allocator_type::deallocate(element, 1);
430 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
432 * \b Complexity: Logarithmic.
435 void update (handle_type handle, const_reference v)
437 if (super_t::operator()(super_t::get_value(handle.node_->value), v))
444 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
446 * \b Complexity: Logarithmic.
448 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
450 void update (handle_type handle)
452 node_pointer this_node = handle.node_;
454 if (this_node->parent) {
455 if (super_t::operator()(super_t::get_value(this_node->parent->value), super_t::get_value(this_node->value)))
465 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
467 * \b Complexity: Logarithmic.
469 * \b Note: The new value is expected to be greater than the current one
471 void increase (handle_type handle, const_reference v)
473 handle.node_->value = super_t::make_node(v);
478 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
480 * \b Complexity: Logarithmic.
482 * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
484 void increase (handle_type handle)
486 node_pointer n = handle.node_;
489 update_top_element();
494 * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
496 * \b Complexity: Logarithmic.
498 * \b Note: The new value is expected to be less than the current one
500 void decrease (handle_type handle, const_reference v)
502 handle.node_->value = super_t::make_node(v);
507 * \b Effects: Updates the heap after the element handled by \c handle has been changed.
509 * \b Complexity: Logarithmic.
511 * \b 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!
513 void decrease (handle_type handle)
515 node_pointer n = handle.node_;
519 update_top_element();
523 * \b Effects: Merge with priority queue rhs.
525 * \b Complexity: Logarithmic.
528 void merge(binomial_heap & rhs)
538 size_type new_size = size_holder::get_size() + rhs.get_size();
539 merge_and_clear_nodes(rhs);
541 size_holder::set_size(new_size);
543 rhs.top_element = NULL;
545 super_t::set_stability_count((std::max)(super_t::get_stability_count(),
546 rhs.get_stability_count()));
547 rhs.set_stability_count(0);
551 /// \copydoc boost::heap::priority_queue::begin
552 iterator begin(void) const
554 return iterator(trees.begin());
557 /// \copydoc boost::heap::priority_queue::end
558 iterator end(void) const
560 return iterator(trees.end());
563 /// \copydoc boost::heap::fibonacci_heap::ordered_begin
564 ordered_iterator ordered_begin(void) const
566 return ordered_iterator(trees.begin(), trees.end(), top_element, super_t::value_comp());
569 /// \copydoc boost::heap::fibonacci_heap::ordered_end
570 ordered_iterator ordered_end(void) const
572 return ordered_iterator(NULL, super_t::value_comp());
576 * \b Effects: Removes the element handled by \c handle from the priority_queue.
578 * \b Complexity: Logarithmic.
580 void erase(handle_type handle)
582 node_pointer n = handle.node_;
583 siftup(n, force_inf());
588 /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
589 static handle_type s_handle_from_iterator(iterator const & it)
591 node_type * ptr = const_cast<node_type *>(it.get_node());
592 return handle_type(ptr);
595 /// \copydoc boost::heap::priority_queue::value_comp
596 value_compare const & value_comp(void) const
598 return super_t::value_comp();
601 /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
602 template <typename HeapType>
603 bool operator<(HeapType const & rhs) const
605 return detail::heap_compare(*this, rhs);
608 /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
609 template <typename HeapType>
610 bool operator>(HeapType const & rhs) const
612 return detail::heap_compare(rhs, *this);
615 /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
616 template <typename HeapType>
617 bool operator>=(HeapType const & rhs) const
619 return !operator<(rhs);
622 /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
623 template <typename HeapType>
624 bool operator<=(HeapType const & rhs) const
626 return !operator>(rhs);
629 /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
630 template <typename HeapType>
631 bool operator==(HeapType const & rhs) const
633 return detail::heap_equality(*this, rhs);
636 /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
637 template <typename HeapType>
638 bool operator!=(HeapType const & rhs) const
640 return !(*this == rhs);
644 #if !defined(BOOST_DOXYGEN_INVOKED)
645 void merge_and_clear_nodes(binomial_heap & rhs)
647 BOOST_HEAP_ASSERT (!empty());
648 BOOST_HEAP_ASSERT (!rhs.empty());
650 node_list_iterator this_iterator = trees.begin();
651 node_pointer carry_node = NULL;
653 while (!rhs.trees.empty()) {
654 node_pointer rhs_node = static_cast<node_pointer>(&rhs.trees.front());
655 size_type rhs_degree = rhs_node->child_count();
657 if (super_t::operator()(top_element->value, rhs_node->value))
658 top_element = rhs_node;
661 node_pointer this_node = static_cast<node_pointer>(&*this_iterator);
662 size_type this_degree = this_node->child_count();
664 rhs.sorted_by_degree();
666 if (this_degree == rhs_degree) {
668 if (carry_node->child_count() < this_degree) {
669 trees.insert(this_iterator, *carry_node);
672 rhs.trees.pop_front();
673 carry_node = merge_trees(carry_node, rhs_node);
677 this_iterator = trees.erase(this_iterator);
678 rhs.trees.pop_front();
679 carry_node = merge_trees(this_node, rhs_node);
682 if (this_iterator == trees.end())
688 if (this_degree < rhs_degree) {
690 if (carry_node->child_count() < this_degree) {
691 trees.insert(this_iterator, *carry_node);
694 } else if (carry_node->child_count() == rhs_degree) {
695 rhs.trees.pop_front();
696 carry_node = merge_trees(carry_node, rhs_node);
699 this_iterator = trees.erase(this_iterator);
700 carry_node = merge_trees(this_node, carry_node);
705 if (this_iterator == trees.end())
710 if (this_iterator == trees.end())
716 if (this_degree > rhs_degree) {
717 rhs.trees.pop_front();
719 if (carry_node->child_count() < rhs_degree) {
720 trees.insert(this_iterator, *carry_node);
721 trees.insert(this_iterator, *rhs_node);
724 carry_node = merge_trees(rhs_node, carry_node);
726 trees.insert(this_iterator, *rhs_node);
730 if (!rhs.trees.empty()) {
732 node_list_iterator rhs_it = rhs.trees.begin();
733 while (static_cast<node_pointer>(&*rhs_it)->child_count() < carry_node->child_count())
735 rhs.insert_node(rhs_it, carry_node);
738 rhs.sorted_by_degree();
740 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
741 update_top_element();
743 merge_and_clear_nodes(rhs);
745 trees.splice(trees.end(), rhs.trees, rhs.trees.begin(), rhs.trees.end());
750 insert_node(this_iterator, carry_node);
753 void clone_forest(binomial_heap const & rhs)
755 BOOST_HEAP_ASSERT(trees.empty());
756 typedef typename node_type::template node_cloner<allocator_type> node_cloner;
757 trees.clone_from(rhs.trees, node_cloner(*this, NULL), detail::nop_disposer());
759 update_top_element();
764 template <typename X>
765 bool operator()(X const &, X const &) const
771 template <typename Compare>
772 void siftup(node_pointer n, Compare const & cmp)
775 node_pointer parent = n->parent;
776 node_pointer grand_parent = parent->parent;
777 if (cmp(n->value, parent->value))
780 n->remove_from_parent();
782 n->swap_children(parent);
783 n->update_children();
784 parent->update_children();
787 parent->remove_from_parent();
788 grand_parent->add_child(n);
790 node_list_iterator it = trees.erase(node_list_type::s_iterator_to(*parent));
791 trees.insert(it, *n);
793 n->add_child(parent);
797 void siftdown(node_pointer n)
799 while (n->child_count()) {
800 node_pointer max_child = detail::find_max_child<node_list_type, node_type, internal_compare>(n->children, super_t::get_internal_cmp());
802 if (super_t::operator()(max_child->value, n->value))
805 max_child->remove_from_parent();
807 n->swap_children(max_child);
808 n->update_children();
809 max_child->update_children();
811 node_pointer parent = n->parent;
813 n->remove_from_parent();
814 max_child->add_child(n);
815 parent->add_child(max_child);
817 node_list_iterator position = trees.erase(node_list_type::s_iterator_to(*n));
818 max_child->add_child(n);
819 trees.insert(position, *max_child);
824 void insert_node(node_list_iterator it, node_pointer n)
826 if (it != trees.end())
827 BOOST_HEAP_ASSERT(static_cast<node_pointer>(&*it)->child_count() >= n->child_count());
830 BOOST_HEAP_ASSERT(!n->is_linked());
831 if (it == trees.end())
834 node_pointer this_node = static_cast<node_pointer>(&*it);
835 size_type this_degree = this_node->child_count();
836 size_type n_degree = n->child_count();
837 if (this_degree == n_degree) {
838 BOOST_HEAP_ASSERT(it->is_linked());
839 it = trees.erase(it);
841 n = merge_trees(n, this_node);
845 trees.insert(it, *n);
848 // private constructor, just used in pop()
849 explicit binomial_heap(value_compare const & cmp, node_list_type & child_list, size_type size):
852 size_holder::set_size(size);
854 top_element = static_cast<node_pointer>(&*child_list.begin()); // not correct, but we will reset it later
858 for (node_list_iterator it = child_list.begin(); it != child_list.end(); ++it) {
859 node_pointer n = static_cast<node_pointer>(&*it);
863 trees.splice(trees.end(), child_list, child_list.begin(), child_list.end());
865 trees.sort(detail::cmp_by_degree<node_type>());
868 node_pointer merge_trees (node_pointer node1, node_pointer node2)
870 BOOST_HEAP_ASSERT(node1->child_count() == node2->child_count());
872 if (super_t::operator()(node1->value, node2->value))
873 std::swap(node1, node2);
876 node2->remove_from_parent();
878 node1->add_child(node2);
882 void update_top_element(void)
884 top_element = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
887 void sorted_by_degree(void) const
889 #ifdef BOOST_HEAP_SANITYCHECKS
892 for (node_list_const_iterator it = trees.begin(); it != trees.end(); ++it) {
893 const_node_pointer n = static_cast<const_node_pointer>(&*it);
894 BOOST_HEAP_ASSERT(int(n->child_count()) > degree);
895 degree = n->child_count();
897 BOOST_HEAP_ASSERT((detail::is_heap<node_type, super_t>(n, *this)));
899 size_type child_nodes = detail::count_nodes<node_type>(n);
900 BOOST_HEAP_ASSERT(child_nodes == size_type(1 << static_cast<const_node_pointer>(&*it)->child_count()));
905 void sanity_check(void)
907 #ifdef BOOST_HEAP_SANITYCHECKS
911 node_pointer found_top = detail::find_max_child<node_list_type, node_type, internal_compare>(trees, super_t::get_internal_cmp());
912 BOOST_HEAP_ASSERT(top_element == found_top);
915 if (constant_time_size) {
916 size_t counted = detail::count_list_nodes<node_type, node_list_type>(trees);
917 size_t stored = size_holder::get_size();
918 BOOST_HEAP_ASSERT(counted == stored);
923 node_pointer top_element;
924 node_list_type trees;
925 #endif // BOOST_DOXYGEN_INVOKED
929 } /* namespace heap */
930 } /* namespace boost */
932 #undef BOOST_HEAP_ASSERT
934 #endif /* BOOST_HEAP_D_ARY_HEAP_HPP */