boost/heap/pairing_heap.hpp

0001 // boost heap: pairing heap
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_PAIRING_HEAP_HPP
0010 #define BOOST_HEAP_PAIRING_HEAP_HPP
0011
0012 #include <algorithm>
0013 #include <type_traits>
0014 #include <utility>
0015
0016 #include <boost/assert.hpp>
0017
0018 #include <boost/heap/detail/heap_comparison.hpp>
0019 #include <boost/heap/detail/heap_node.hpp>
0020 #include <boost/heap/detail/stable_heap.hpp>
0021 #include <boost/heap/detail/tree_iterator.hpp>
0022 #include <boost/heap/policies.hpp>
0023
0024 #ifdef BOOST_HAS_PRAGMA_ONCE
0025 #    pragma once
0026 #endif
0027
0028
0029 #ifndef BOOST_DOXYGEN_INVOKED
0030 #    ifdef BOOST_HEAP_SANITYCHECKS
0031 #        define BOOST_HEAP_ASSERT BOOST_ASSERT
0032 #    else
0033 #        define BOOST_HEAP_ASSERT( expression ) static_assert( true, "force semicolon" )
0034 #    endif
0035 #endif
0036
0037 namespace boost { namespace heap {
0038 namespace detail {
0039
0040 typedef parameter::parameters< boost::parameter::optional< tag::allocator >,
0041                                boost::parameter::optional< tag::compare >,
0042                                boost::parameter::optional< tag::stable >,
0043                                boost::parameter::optional< tag::constant_time_size >,
0044                                boost::parameter::optional< tag::stability_counter_type > >
0045     pairing_heap_signature;
0046
0047 template < typename T, typename Parspec >
0048 struct make_pairing_heap_base
0049 {
0050     static const bool constant_time_size
0051         = parameter::binding< Parspec, tag::constant_time_size, std::true_type >::type::value;
0052     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::type               base_type;
0053     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::allocator_argument allocator_argument;
0054     typedef typename detail::make_heap_base< T, Parspec, constant_time_size >::compare_argument   compare_argument;
0055
0056     typedef heap_node< typename base_type::internal_type, false > node_type;
0057
0058     typedef typename boost::allocator_rebind< allocator_argument, node_type >::type allocator_type;
0059
0060     struct type : base_type, allocator_type
0061     {
0062         type( compare_argument const& arg ) :
0063             base_type( arg )
0064         {}
0065
0066         type( allocator_type const& arg ) :
0067             allocator_type( arg )
0068         {}
0069
0070         type( type const& rhs ) :
0071             base_type( rhs ),
0072             allocator_type( rhs )
0073         {}
0074
0075         type( type&& rhs ) :
0076             base_type( std::move( static_cast< base_type& >( rhs ) ) ),
0077             allocator_type( std::move( static_cast< allocator_type& >( rhs ) ) )
0078         {}
0079
0080         type& operator=( type&& rhs )
0081         {
0082             base_type::operator=( std::move( static_cast< base_type& >( rhs ) ) );
0083             allocator_type::operator=( std::move( static_cast< allocator_type& >( rhs ) ) );
0084             return *this;
0085         }
0086
0087         type& operator=( type const& rhs )
0088         {
0089             base_type::operator=( static_cast< base_type const& >( rhs ) );
0090             allocator_type::operator=( static_cast< const allocator_type& >( rhs ) );
0091             return *this;
0092         }
0093     };
0094 };
0095
0096 } // namespace detail
0097
0098 /**
0099  * \class pairing_heap
0100  * \brief pairing heap
0101  *
0102  * Pairing heaps are self-adjusting binary heaps. Although design and implementation are rather simple,
0103  * the complexity analysis is yet unsolved. For details, consult:
0104  *
0105  * Pettie, Seth (2005), "Towards a final analysis of pairing heaps",
0106  * Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174-183
0107  *
0108  * The template parameter T is the type to be managed by the container.
0109  * The user can specify additional options and if no options are provided default options are used.
0110  *
0111  * The container supports the following options:
0112  * - \c boost::heap::compare<>, defaults to \c compare<std::less<T> >
0113  * - \c boost::heap::stable<>, defaults to \c stable<false>
0114  * - \c boost::heap::stability_counter_type<>, defaults to \c stability_counter_type<boost::uintmax_t>
0115  * - \c boost::heap::allocator<>, defaults to \c allocator<std::allocator<T> >
0116  * - \c boost::heap::constant_time_size<>, defaults to \c constant_time_size<true>
0117  *
0118  *
0119  */
0120 #ifdef BOOST_DOXYGEN_INVOKED
0121 template < class T, class... Options >
0122 #else
0123 template < typename T,
0124            class A0 = boost::parameter::void_,
0125            class A1 = boost::parameter::void_,
0126            class A2 = boost::parameter::void_,
0127            class A3 = boost::parameter::void_,
0128            class A4 = boost::parameter::void_ >
0129 #endif
0130 class pairing_heap :
0131     private detail::make_pairing_heap_base< T, typename detail::pairing_heap_signature::bind< A0, A1, A2, A3, A4 >::type >::type
0132 {
0133     typedef typename detail::pairing_heap_signature::bind< A0, A1, A2, A3, A4 >::type bound_args;
0134     typedef detail::make_pairing_heap_base< T, bound_args >                           base_maker;
0135     typedef typename base_maker::type                                                 super_t;
0136
0137     typedef typename super_t::internal_type         internal_type;
0138     typedef typename super_t::size_holder_type      size_holder;
0139     typedef typename base_maker::allocator_argument allocator_argument;
0140
0141 private:
0142     template < typename Heap1, typename Heap2 >
0143     friend struct heap_merge_emulate;
0144
0145 #ifndef BOOST_DOXYGEN_INVOKED
0146     struct implementation_defined : detail::extract_allocator_types< typename base_maker::allocator_argument >
0147     {
0148         typedef T value_type;
0149         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::size_type size_type;
0150         typedef typename detail::extract_allocator_types< typename base_maker::allocator_argument >::reference reference;
0151
0152         typedef typename base_maker::compare_argument value_compare;
0153         typedef typename base_maker::allocator_type   allocator_type;
0154
0155         typedef typename boost::allocator_pointer< allocator_type >::type       node_pointer;
0156         typedef typename boost::allocator_const_pointer< allocator_type >::type const_node_pointer;
0157
0158         typedef detail::heap_node_list                  node_list_type;
0159         typedef typename node_list_type::iterator       node_list_iterator;
0160         typedef typename node_list_type::const_iterator node_list_const_iterator;
0161
0162         typedef typename base_maker::node_type node;
0163
0164         typedef detail::value_extractor< value_type, internal_type, super_t > value_extractor;
0165         typedef typename super_t::internal_compare                            internal_compare;
0166         typedef detail::node_handle< node_pointer, super_t, reference >       handle_type;
0167
0168         typedef detail::tree_iterator< node,
0169                                        const value_type,
0170                                        allocator_type,
0171                                        value_extractor,
0172                                        detail::pointer_to_reference< node >,
0173                                        false,
0174                                        false,
0175                                        value_compare >
0176             iterator;
0177
0178         typedef iterator const_iterator;
0179
0180         typedef detail::tree_iterator< node,
0181                                        const value_type,
0182                                        allocator_type,
0183                                        value_extractor,
0184                                        detail::pointer_to_reference< node >,
0185                                        false,
0186                                        true,
0187                                        value_compare >
0188             ordered_iterator;
0189     };
0190
0191     typedef typename implementation_defined::node                     node;
0192     typedef typename implementation_defined::node_pointer             node_pointer;
0193     typedef typename implementation_defined::node_list_type           node_list_type;
0194     typedef typename implementation_defined::node_list_iterator       node_list_iterator;
0195     typedef typename implementation_defined::node_list_const_iterator node_list_const_iterator;
0196     typedef typename implementation_defined::internal_compare         internal_compare;
0197
0198     typedef boost::intrusive::list< detail::heap_node_base< true >, boost::intrusive::constant_time_size< false > >
0199         node_child_list;
0200 #endif
0201
0202 public:
0203     typedef T value_type;
0204
0205     typedef typename implementation_defined::size_type        size_type;
0206     typedef typename implementation_defined::difference_type  difference_type;
0207     typedef typename implementation_defined::value_compare    value_compare;
0208     typedef typename implementation_defined::allocator_type   allocator_type;
0209     typedef typename implementation_defined::reference        reference;
0210     typedef typename implementation_defined::const_reference  const_reference;
0211     typedef typename implementation_defined::pointer          pointer;
0212     typedef typename implementation_defined::const_pointer    const_pointer;
0213     /// \copydoc boost::heap::priority_queue::iterator
0214     typedef typename implementation_defined::iterator         iterator;
0215     typedef typename implementation_defined::const_iterator   const_iterator;
0216     typedef typename implementation_defined::ordered_iterator ordered_iterator;
0217
0218     typedef typename implementation_defined::handle_type handle_type;
0219
0220     static const bool constant_time_size    = super_t::constant_time_size;
0221     static const bool has_ordered_iterators = true;
0222     static const bool is_mergable           = true;
0223     static const bool is_stable             = detail::extract_stable< bound_args >::value;
0224     static const bool has_reserve           = false;
0225
0226     /// \copydoc boost::heap::priority_queue::priority_queue(value_compare const &)
0227     explicit pairing_heap( value_compare const& cmp = value_compare() ) :
0228         super_t( cmp ),
0229         root( nullptr )
0230     {}
0231
0232     /// \copydoc boost::heap::priority_queue::priority_queue(allocator_type const &)
0233     explicit pairing_heap( allocator_type const& alloc ) :
0234         super_t( alloc ),
0235         root( nullptr )
0236     {}
0237
0238     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue const &)
0239     pairing_heap( pairing_heap const& rhs ) :
0240         super_t( rhs ),
0241         root( nullptr )
0242     {
0243         if ( rhs.empty() )
0244             return;
0245
0246         clone_tree( rhs );
0247         size_holder::set_size( rhs.get_size() );
0248     }
0249
0250     /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
0251     pairing_heap( pairing_heap&& rhs ) :
0252         super_t( std::move( rhs ) ),
0253         root( rhs.root )
0254     {
0255         rhs.root = nullptr;
0256     }
0257
0258     /// \copydoc boost::heap::priority_queue::operator=(priority_queue &&)
0259     pairing_heap& operator=( pairing_heap&& rhs )
0260     {
0261         super_t::operator=( std::move( rhs ) );
0262         root     = rhs.root;
0263         rhs.root = nullptr;
0264         return *this;
0265     }
0266
0267     /// \copydoc boost::heap::priority_queue::operator=(priority_queue const & rhs)
0268     pairing_heap& operator=( pairing_heap const& rhs )
0269     {
0270         clear();
0271         size_holder::set_size( rhs.get_size() );
0272         static_cast< super_t& >( *this ) = rhs;
0273
0274         clone_tree( rhs );
0275         return *this;
0276     }
0277
0278     ~pairing_heap( void )
0279     {
0280         while ( !empty() )
0281             pop();
0282     }
0283
0284     /// \copydoc boost::heap::priority_queue::empty
0285     bool empty( void ) const
0286     {
0287         return root == nullptr;
0288     }
0289
0290     /// \copydoc boost::heap::binomial_heap::size
0291     size_type size( void ) const
0292     {
0293         if ( constant_time_size )
0294             return size_holder::get_size();
0295
0296         if ( root == nullptr )
0297             return 0;
0298         else
0299             return detail::count_nodes( root );
0300     }
0301
0302     /// \copydoc boost::heap::priority_queue::max_size
0303     size_type max_size( void ) const
0304     {
0305         const allocator_type& alloc = *this;
0306         return boost::allocator_max_size( alloc );
0307     }
0308
0309     /// \copydoc boost::heap::priority_queue::clear
0310     void clear( void )
0311     {
0312         if ( empty() )
0313             return;
0314
0315         root->template clear_subtree< allocator_type >( *this );
0316         root->~node();
0317         allocator_type& alloc = *this;
0318         alloc.deallocate( root, 1 );
0319         root = nullptr;
0320         size_holder::set_size( 0 );
0321     }
0322
0323     /// \copydoc boost::heap::priority_queue::get_allocator
0324     allocator_type get_allocator( void ) const
0325     {
0326         return *this;
0327     }
0328
0329     /// \copydoc boost::heap::priority_queue::swap
0330     void swap( pairing_heap& rhs )
0331     {
0332         super_t::swap( rhs );
0333         std::swap( root, rhs.root );
0334     }
0335
0336
0337     /// \copydoc boost::heap::priority_queue::top
0338     const_reference top( void ) const
0339     {
0340         BOOST_ASSERT( !empty() );
0341
0342         return super_t::get_value( root->value );
0343     }
0344
0345     /**
0346      * \b Effects: Adds a new element to the priority queue. Returns handle to element
0347      *
0348      * \cond
0349      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0350      * \endcond
0351      *
0352      * \b Complexity: 2**2*log(log(N)) (amortized).
0353      *
0354      * */
0355     handle_type push( value_type const& v )
0356     {
0357         size_holder::increment();
0358
0359         allocator_type& alloc = *this;
0360         node_pointer    n     = alloc.allocate( 1 );
0361         new ( n ) node( super_t::make_node( v ) );
0362         merge_node( n );
0363         return handle_type( n );
0364     }
0365
0366     /**
0367      * \b Effects: Adds a new element to the priority queue. The element is directly constructed in-place. Returns
0368      * handle to element.
0369      *
0370      * \cond
0371      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0372      * \endcond
0373      *
0374      * \b Complexity: 2**2*log(log(N)) (amortized).
0375      *
0376      * */
0377     template < class... Args >
0378     handle_type emplace( Args&&... args )
0379     {
0380         size_holder::increment();
0381
0382         allocator_type& alloc = *this;
0383         node_pointer    n     = alloc.allocate( 1 );
0384         new ( n ) node( super_t::make_node( std::forward< Args >( args )... ) );
0385         merge_node( n );
0386         return handle_type( n );
0387     }
0388
0389     /**
0390      * \b Effects: Removes the top element from the priority queue.
0391      *
0392      * \b Complexity: Logarithmic (amortized).
0393      *
0394      * */
0395     void pop( void )
0396     {
0397         BOOST_ASSERT( !empty() );
0398
0399         erase( handle_type( root ) );
0400     }
0401
0402     /**
0403      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0404      *
0405      * \cond
0406      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0407      * \endcond
0408      *
0409      * \b Complexity: 2**2*log(log(N)) (amortized).
0410      *
0411      * */
0412     void update( handle_type handle, const_reference v )
0413     {
0414         handle.node_->value = super_t::make_node( v );
0415         update( handle );
0416     }
0417
0418     /**
0419      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0420      *
0421      * \cond
0422      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0423      * \endcond
0424      *
0425      * \b Complexity: 2**2*log(log(N)) (amortized).
0426      *
0427      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0428      * */
0429     void update( handle_type handle )
0430     {
0431         node_pointer n = handle.node_;
0432
0433         n->unlink();
0434         if ( !n->children.empty() )
0435             n = merge_nodes( n, merge_node_list( n->children ) );
0436
0437         if ( n != root )
0438             merge_node( n );
0439     }
0440
0441     /**
0442      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0443      *
0444      * \cond
0445      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0446      * \endcond
0447      *
0448      * \b Complexity: 2**2*log(log(N)) (amortized).
0449      *
0450      * \b Note: The new value is expected to be greater than the current one
0451      * */
0452     void increase( handle_type handle, const_reference v )
0453     {
0454         update( handle, v );
0455     }
0456
0457     /**
0458      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0459      *
0460      * \cond
0461      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0462      * \endcond
0463      *
0464      * \b Complexity: 2**2*log(log(N)) (amortized).
0465      *
0466      * \b Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
0467      * */
0468     void increase( handle_type handle )
0469     {
0470         update( handle );
0471     }
0472
0473     /**
0474      * \b Effects: Assigns \c v to the element handled by \c handle & updates the priority queue.
0475      *
0476      * \cond
0477      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0478      * \endcond
0479      *
0480      * \b Complexity: 2**2*log(log(N)) (amortized).
0481      *
0482      * \b Note: The new value is expected to be less than the current one
0483      * */
0484     void decrease( handle_type handle, const_reference v )
0485     {
0486         update( handle, v );
0487     }
0488
0489     /**
0490      * \b Effects: Updates the heap after the element handled by \c handle has been changed.
0491      *
0492      * \cond
0493      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0494      * \endcond
0495      *
0496      * \b Complexity: 2**2*log(log(N)) (amortized).
0497      *
0498      * \b Note: The new value is expected to be less than the current one. If this is not called, after a handle has
0499      * been updated, the behavior of the data structure is undefined!
0500      * */
0501     void decrease( handle_type handle )
0502     {
0503         update( handle );
0504     }
0505
0506     /**
0507      * \b Effects: Removes the element handled by \c handle from the priority_queue.
0508      *
0509      * \cond
0510      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0511      * \endcond
0512      *
0513      * \b Complexity: 2**2*log(log(N)) (amortized).
0514      * */
0515     void erase( handle_type handle )
0516     {
0517         node_pointer n = handle.node_;
0518         if ( n != root ) {
0519             n->unlink();
0520             if ( !n->children.empty() )
0521                 merge_node( merge_node_list( n->children ) );
0522         } else {
0523             if ( !n->children.empty() )
0524                 root = merge_node_list( n->children );
0525             else
0526                 root = nullptr;
0527         }
0528
0529         size_holder::decrement();
0530         n->~node();
0531         allocator_type& alloc = *this;
0532         alloc.deallocate( n, 1 );
0533     }
0534
0535     /// \copydoc boost::heap::priority_queue::begin
0536     iterator begin( void ) const
0537     {
0538         return iterator( root, super_t::value_comp() );
0539     }
0540
0541     /// \copydoc boost::heap::priority_queue::end
0542     iterator end( void ) const
0543     {
0544         return iterator( super_t::value_comp() );
0545     }
0546
0547     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
0548     ordered_iterator ordered_begin( void ) const
0549     {
0550         return ordered_iterator( root, super_t::value_comp() );
0551     }
0552
0553     /// \copydoc boost::heap::fibonacci_heap::ordered_begin
0554     ordered_iterator ordered_end( void ) const
0555     {
0556         return ordered_iterator( nullptr, super_t::value_comp() );
0557     }
0558
0559
0560     /// \copydoc boost::heap::d_ary_heap_mutable::s_handle_from_iterator
0561     static handle_type s_handle_from_iterator( iterator const& it )
0562     {
0563         node* ptr = const_cast< node* >( it.get_node() );
0564         return handle_type( ptr );
0565     }
0566
0567     /**
0568      * \b Effects: Merge all elements from rhs into this
0569      *
0570      * \cond
0571      * \b Complexity: \f$2^2log(log(N))\f$ (amortized).
0572      * \endcond
0573      *
0574      * \b Complexity: 2**2*log(log(N)) (amortized).
0575      *
0576      * */
0577     void merge( pairing_heap& rhs )
0578     {
0579         if ( rhs.empty() )
0580             return;
0581
0582         merge_node( rhs.root );
0583
0584         size_holder::add( rhs.get_size() );
0585         rhs.set_size( 0 );
0586         rhs.root = nullptr;
0587
0588         super_t::set_stability_count( ( std::max )( super_t::get_stability_count(), rhs.get_stability_count() ) );
0589         rhs.set_stability_count( 0 );
0590     }
0591
0592     /// \copydoc boost::heap::priority_queue::value_comp
0593     value_compare const& value_comp( void ) const
0594     {
0595         return super_t::value_comp();
0596     }
0597
0598     /// \copydoc boost::heap::priority_queue::operator<(HeapType const & rhs) const
0599     template < typename HeapType >
0600     bool operator<( HeapType const& rhs ) const
0601     {
0602         return detail::heap_compare( *this, rhs );
0603     }
0604
0605     /// \copydoc boost::heap::priority_queue::operator>(HeapType const & rhs) const
0606     template < typename HeapType >
0607     bool operator>( HeapType const& rhs ) const
0608     {
0609         return detail::heap_compare( rhs, *this );
0610     }
0611
0612     /// \copydoc boost::heap::priority_queue::operator>=(HeapType const & rhs) const
0613     template < typename HeapType >
0614     bool operator>=( HeapType const& rhs ) const
0615     {
0616         return !operator<( rhs );
0617     }
0618
0619     /// \copydoc boost::heap::priority_queue::operator<=(HeapType const & rhs) const
0620     template < typename HeapType >
0621     bool operator<=( HeapType const& rhs ) const
0622     {
0623         return !operator>( rhs );
0624     }
0625
0626     /// \copydoc boost::heap::priority_queue::operator==(HeapType const & rhs) const
0627     template < typename HeapType >
0628     bool operator==( HeapType const& rhs ) const
0629     {
0630         return detail::heap_equality( *this, rhs );
0631     }
0632
0633     /// \copydoc boost::heap::priority_queue::operator!=(HeapType const & rhs) const
0634     template < typename HeapType >
0635     bool operator!=( HeapType const& rhs ) const
0636     {
0637         return !( *this == rhs );
0638     }
0639
0640 private:
0641 #if !defined( BOOST_DOXYGEN_INVOKED )
0642     void clone_tree( pairing_heap const& rhs )
0643     {
0644         BOOST_HEAP_ASSERT( root == nullptr );
0645         if ( rhs.empty() )
0646             return;
0647
0648         root = allocator_type::allocate( 1 );
0649
0650         new ( root ) node( static_cast< node const& >( *rhs.root ), static_cast< allocator_type& >( *this ) );
0651     }
0652
0653     void merge_node( node_pointer other )
0654     {
0655         BOOST_HEAP_ASSERT( other );
0656         if ( root != nullptr )
0657             root = merge_nodes( root, other );
0658         else
0659             root = other;
0660     }
0661
0662     node_pointer merge_node_list( node_child_list& children )
0663     {
0664         BOOST_HEAP_ASSERT( !children.empty() );
0665         node_pointer merged = merge_first_pair( children );
0666         if ( children.empty() )
0667             return merged;
0668
0669         node_child_list node_list;
0670         node_list.push_back( *merged );
0671
0672         do {
0673             node_pointer next_merged = merge_first_pair( children );
0674             node_list.push_back( *next_merged );
0675         } while ( !children.empty() );
0676
0677         return merge_node_list( node_list );
0678     }
0679
0680     node_pointer merge_first_pair( node_child_list& children )
0681     {
0682         BOOST_HEAP_ASSERT( !children.empty() );
0683         node_pointer first_child = static_cast< node_pointer >( &children.front() );
0684         children.pop_front();
0685         if ( children.empty() )
0686             return first_child;
0687
0688         node_pointer second_child = static_cast< node_pointer >( &children.front() );
0689         children.pop_front();
0690
0691         return merge_nodes( first_child, second_child );
0692     }
0693
0694     node_pointer merge_nodes( node_pointer node1, node_pointer node2 )
0695     {
0696         if ( super_t::operator()( node1->value, node2->value ) )
0697             std::swap( node1, node2 );
0698
0699         node2->unlink();
0700         node1->children.push_front( *node2 );
0701         return node1;
0702     }
0703
0704     node_pointer root;
0705 #endif
0706 };
0707
0708
0709 }} // namespace boost::heap
0710
0711 #undef BOOST_HEAP_ASSERT
0712 #endif /* BOOST_HEAP_PAIRING_HEAP_HPP */