Imported Upstream version 1.49.0upstream/1.49.0

19 files changed, 2898 insertions, 0 deletions

diff --git a/libs/heap/doc/Jamfile.v2 b/libs/heap/doc/Jamfile.v2
new file mode 100644
index 0000000000..c4b46465c8
--- /dev/null
+++ b/libs/heap/doc/Jamfile.v2
@@ -0,0 +1,52 @@
+# Copyright 2010 Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0. (See accompanying
+# file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import doxygen ;
+import quickbook ;
+
+doxygen autodoc
+    :
+        [ glob ../../../boost/heap/*.hpp ] ../../../boost/heap/detail/mutable_heap.hpp
+    :
+        #<doxygen:param>EXTRACT_ALL=YES
+        <doxygen:param>"PREDEFINED=\"BOOST_DOXYGEN_INVOKED\" \\
+                                   \"BOOST_DEDUCED_TYPENAME=typename\" \\
+                                   \"BOOST_HAS_RVALUE_REFS\" \\
+                                   "
+        <doxygen:param>HIDE_UNDOC_MEMBERS=YES
+        <doxygen:param>HIDE_UNDOC_CLASSES=YES
+        <doxygen:param>INLINE_INHERITED_MEMB=YES
+        <doxygen:param>EXTRACT_PRIVATE=NO
+        <doxygen:param>ENABLE_PREPROCESSING=YES
+        <doxygen:param>MACRO_EXPANSION=YES
+        <doxygen:param>EXPAND_ONLY_PREDEF=YES
+        <doxygen:param>SEARCH_INCLUDES=YES
+        <doxygen:param>INCLUDE_PATH=$(BOOST_ROOT)
+        <doxygen:param>EXAMPLE_PATH=$(BOOST_ROOT)/libs/heap/examples
+        <doxygen:param>BRIEF_MEMBER_DESC=YES
+        <doxygen:param>REPEAT_BRIEF=YES
+        <doxygen:param>ALWAYS_DETAILED_SEC=YES
+        <doxygen:param>MULTILINE_CPP_IS_BRIEF=YES
+    ;
+
+xml heap : heap.qbk : ;
+
+boostbook standalone
+    : heap
+    : <xsl:param>html.stylesheet=boostbook.css
+      <xsl:param>boost.root=../../../..
+      <xsl:param>boost.libraries=../../../libraries.htm
+      <xsl:param>toc.max.depth=3
+      <xsl:param>toc.section.depth=1
+      <xsl:param>chunk.section.depth=1
+      <dependency>autodoc
+      <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/libs/heap/doc/html
+    ;
+
+install css : [ glob $(BOOST_ROOT)/doc/src/*.css ]
+    : <location>html ;
+install images : [ glob $(BOOST_ROOT)/doc/src/images/*.png ]
+    : <location>html/images ;
+explicit css ;
+explicit images ;
diff --git a/libs/heap/doc/heap.qbk b/libs/heap/doc/heap.qbk
new file mode 100644
index 0000000000..494f228300
--- /dev/null
+++ b/libs/heap/doc/heap.qbk
@@ -0,0 +1,422 @@
+[library Boost.Heap
+    [quickbook 1.4]
+    [authors [Blechmann, Tim]]
+    [copyright 2010-2011 Tim Blechmann]
+    [category algorithms]
+    [purpose
+        heap data structures
+    ]
+    [id heap]
+    [dirname heap]
+    [license
+        Distributed under the Boost Software License, Version 1.0.
+        (See accompanying file LICENSE_1_0.txt or copy at
+        [@http://www.boost.org/LICENSE_1_0.txt])
+    ]
+]
+
+[c++]
+
+
+[/  Links   ]
+
+[def _heap_                      [^boost.heap]]
+
+[/  unspecified stuff   ]
+[def __unspecified_int__ /unspecified-int-type/]
+[def __unspecified__ /unspecified/]
+[def __unspecified_bool__ /unspecified-bool-type/]
+
+[section Introduction & Motivation]
+
+_heap_ is an implementation of priority queues. Priority queues are queue data structures, that order their elements by
+a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality.
+To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and
+different performance characteristics. Especially, it deals with additional aspects:
+
+* *Mutability*: The priority of heap elements can be modified.
+* *Iterators*: Heaps provide iterators to iterate all elements.
+* *Mergable*: While all heaps can be merged, some can be merged efficiently.
+* *Stability*: Heaps can be configured to be stable sorted.
+* *Comparison*: Heaps can be compared for equivalence.
+
+[endsect]
+
+[section:concepts Concepts & Interface]
+
+[section:basic Basic Priority Queue Interface]
+
+Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to
+the data structure, accessing the top element (the element with the highest priority), and removing the top element.
+
+[note _heap_ implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to
+the typical textbook design, which uses min-heaps.]
+
+[h5 Synopsis]
+
+    template <typename T, class ...Options>
+    class priority_queue
+    {
+        // types
+        typedef T                   value_type;
+        typedef ``/unspecified/``         size_type;
+        typedef ``/unspecified/``         difference_type;
+
+        typedef ``/unspecified/``         allocator_type;
+        typedef ``/unspecified/``         value_compare;
+
+        typedef ``/unspecified/``         reference;
+        typedef ``/unspecified/``         const_reference;
+        typedef ``/unspecified/``         pointer;
+        typedef ``/unspecified/``         const_pointer;
+
+        // construct/copy/destruct
+        explicit priority_queue(value_compare const & = value_compare());
+        priority_queue(priority_queue const &);
+        priority_queue& operator=(priority_queue const &);
+        priority_queue(priority_queue &&);                  // move semantics (C++11 only)
+        priority_queue& operator=(priority_queue &&);       // move semantics (C++11 only)
+
+        // public member functions
+        ``/unspecified/`` push(const_reference);                  // push new element to heap
+        template<class... Args> void emplace(Args &&...);   // push new element to heap, C++11 only
+        const_reference top() const;                        // return top element
+        void pop();                                         // remove top element
+        void clear();                                       // clear heap
+        size_type size() const;                             // number of elements
+        bool empty() const;                                 // priority queue is empty
+        allocator_type get_allocator(void) const;           // return allocator
+        size_type max_size(void) const;                     // maximal possible size
+        void reserve(size_type);                            // reserve space, only available if (has_reserve == true)
+
+        // heap equivalence
+        template<typename HeapType> bool operator==(HeapType const &) const;
+        template<typename HeapType> bool operator!=(HeapType const &) const;
+
+        // heap comparison
+        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 data members
+        static const bool constant_time_size;               // size() has constant complexity
+        static const bool has_ordered_iterators;            // priority queue has ``[link heap.concepts.iterators ordered iterators]``
+        static const bool is_mergable;                      // priority queue is efficiently ``[link heap.concepts.merge mergable]``
+        static const bool is_stable;                        // priority queue has a ``[link heap.concepts.stability stable heap order]``
+        static const bool has_reserve;                      // priority queue has a reserve() member
+    };
+
+[h5 Example]
+
+[import ../examples/interface.cpp]
+[basic_interface]
+
+[endsect]
+
+
+[section:iterators Priority Queue Iterators]
+
+[h5 Synopsis]
+    class iteratable_heap_interface
+    {
+    public:
+        // types
+        typedef ``/unspecified/``         iterator;
+        typedef ``/unspecified/``         const_iterator;
+        typedef ``/unspecified/``         ordered_iterator;
+
+        // public member functions
+        iterator begin(void) const;
+        iterator end(void) const;
+        ordered_iterator ordered_begin(void) const;
+        ordered_iterator ordered_end(void) const;
+    };
+
+Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means
+they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about
+modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface].
+
+Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate
+iterators, while all const member functions preserve the iterator validity.
+
+[note Some implementations require iterators, that contain a set of elements, that are *discovered*, but not *visited*. Therefore
+copying iterators can be inefficient and should be avoided.]
+
+[h5 Example]
+[iterator_interface]
+
+[section:ordered_iterators Ordered Iterators]
+
+Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements
+of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a
+heap in heap order has an amortized complexity of O(N*log(N)).
+
+[h5 Example]
+[ordered_iterator_interface]
+
+[endsect]
+
+[endsect]
+
+[section:comparing Comparing Priority Queues & Equivalence]
+
+The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two
+heaps element by element using =value_compare=.
+
+[note Depending on the heap type, this operation can be rather expensive, because both data structures need to be traversed in
+heap order. On heaps without ordered iterators, the heap needs to be copied internally. The typical complexity is O(n log(n)).]
+
+[endsect]
+
+
+[section:merge Merging Priority Queues]
+
+
+[h3 Mergable Priority Queues]
+
+[h5 Synopsis]
+    class mergable_heap_interface
+    {
+    public:
+        // public member functions
+        void merge(mergable_heap_interface &);
+    };
+
+_heap_ has a concept of a Mergable Priority Queue. A mergable priority queue can efficiently be merged with a different instance
+of the same type.
+
+[h5 Example]
+[merge_interface]
+
+
+[h3 Heap Merge Algorithms]
+
+_heap_ provides a =heap_merge()= algorithm that is can be used to merge different kinds of heaps. Using this algorithm, all _heap_
+data structures can be merged, although some cannot be merged efficiently.
+
+[h5 Example]
+[heap_merge_algorithm]
+
+[endsect]
+
+[section:mutability Mutability]
+
+Some priority queues of _heap_ are mutable, that means the priority of their elements can be changed. To achieve mutability,
+_heap_ introduces the concept of *handles*, which can be used to access the internal nodes of the priority queue in order to
+change its value and to restore the heap order.
+
+[h5 Synopsis]
+    class mutable_heap_interface
+    {
+    public:
+        typedef ``/unspecified/`` iterator;
+        struct handle_type
+        {
+            value_type & operator*() const;
+        };
+
+        static handle_type s_iterator_to_handle(iterator const &);
+
+        // priority queue interface
+        handle_type push(T const & v);
+
+        // update element via assignment and fix heap
+        void update(handle_type const & handle, value_type const & v);
+        void increase(handle_type const & handle, value_type const & v);
+        void decrease(handle_type const & handle, value_type const & v);
+
+        // fix heap after element has been changed via the handle
+        void update(handle_type const & handle);
+        void increase(handle_type const & handle);
+        void decrease(handle_type const & handle);
+    };
+
+[warning Incorrect use of =increase= or =decrease= may corrupt the priority queue data structure. If unsure use =update= can be
+used at the cost of efficiency.]
+
+[h5 Example]
+[mutable_interface]
+
+Note that handles can be stored inside the =value_type=:
+
+[mutable_interface_handle_in_value]
+
+[h3 The Fixup Interface]
+
+There are two different APIs to support mutability. The first family of functions provides update functionality by changing
+the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after
+an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue
+elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up
+immediately after the priority of the element has been changed.
+
+
+Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient
+than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right
+direction.
+
+[h5 Example]
+
+[mutable_fixup_interface]
+
+Iterators can be coverted to handles using the static member function =s_handle_from_iterator=. However most implementations of
+=update= invalidate all iterators. The most notable exception is the [classref boost::heap::fibonacci_heap fibonacci heap],
+providing a lazy update function, that just invalidates the iterators, that are related to this handle.
+
+[warning After changing the priority via a handle, the heap needs to be fixed by calling one of the update functions. Otherwise the
+priority queue structure may be corrupted!]
+
+[endsect]
+
+[section:stability Stability]
+
+A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as
+they are inserted. The data structures provided by _heap_, can be configured to be stable at compile time using the
+[classref boost::heap::stable] policy. Two notions of stability are supported. If a heap is configured with *no stability*,
+the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by
+their insertion time.
+
+Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node.
+The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be
+configured to use a different type using the [classref boost::heap::stability_counter_type] template argument.
+
+[warning The stability counter is prone to integer overflows. If an overflow occurs during a =push()= call, the operation
+ will fail and an exception is thrown. Later =push()= call will succeed, but the stable heap order will be compromised. However an
+ integer overflow at 64bit is very unlikely: if an application would issue one =push()= operation per microsecond, the value will
+ overflow in more than 500000 years.]
+
+[endsect]
+
+
+[endsect]
+
+[section:data_structures Data Structures]
+_heap_ provides the following data structures:
+
+[variablelist
+    [[[classref boost::heap::priority_queue]]
+     [
+         The [classref boost::heap::priority_queue priority_queue] class is a wrapper to the stl heap functions. It implements
+         a heap as container adaptor ontop of a =std::vector= and is immutable.
+     ]
+    ]
+
+    [[[classref boost::heap::d_ary_heap]]
+     [
+        [@http://en.wikipedia.org/wiki/D-ary_heap D-ary heaps] are a generalization of binary heap with each non-leaf node
+        having N children. For a low arity, the height of the heap is larger, but the number of comparisons to find the largest
+        child node is bigger. D-ary heaps are implemented as container adaptors based on a =std::vector=.
+
+        The data structure can be configured as mutable. This is achieved by storing the values inside a std::list.
+     ]
+    ]
+
+    [[[classref boost::heap::binomial_heap]]
+     [
+        [@http://en.wikipedia.org/wiki/Binomial_heap Binomial heaps] are node-base heaps, that are implemented as a set of
+        binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n).
+        In contrast to d-ary heaps, binomial heaps can also be merged in O(log n).
+     ]
+    ]
+
+    [[[classref boost::heap::fibonacci_heap]]
+     [
+        [@http://en.wikipedia.org/wiki/Fibonacci_heap Fibonacci heaps] are node-base heaps, that are implemented as a forest of
+        heap-ordered trees. They provide better amortized performance than binomial heaps. Except =pop()= and =erase()=, the most
+        important heap operations have constant amortized complexity.
+     ]
+    ]
+
+    [[[classref boost::heap::pairing_heap]]
+     [
+        [@http://en.wikipedia.org/wiki/Pairing_heap Pairing heaps] are self-adjusting node-based 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
+     ]
+    ]
+
+    [[[classref boost::heap::skew_heap]]
+     [
+        [@http://en.wikipedia.org/wiki/Skew_heap Skew heaps] are self-adjusting node-based heaps. Although there are no
+        constraints for the tree structure, all heap operations can be performed in O(log n).
+     ]
+    ]
+]
+
+[table Comparison of amortized complexity
+    [[]                                             [[^top()]]  [[^push()]]     [[^pop()]]  [[^update()]] [[^increase()]]   [[^decrease()]] [[^erase()]] [[^merge_and_clear()]]]
+    [[[classref boost::heap::priority_queue]]       [[^O(1)]]   [O(log(N))]     [O(log(N))] [n/a]         [n/a]             [n/a]           [n/a]        [O((N+M)*log(N+M))]]
+    [[[classref boost::heap::d_ary_heap]]           [[^O(1)]]   [O(log(N))]     [O(log(N))] [O(log(N))]   [O(log(N))]       [O(log(N))]     [O(log(N))]  [O((N+M)*log(N+M))]]
+    [[[classref boost::heap::binomial_heap]]        [[^O(1)]]   [O(log(N))]     [O(log(N))] [O(log(N))]   [O(log(N))]       [O(log(N))]     [O(log(N))]  [O(log(N+M))]]
+    [[[classref boost::heap::fibonacci_heap]]       [[^O(1)]]   [O(1)]          [O(log(N))] [O(log(N))
+        [footnote The fibonacci a [^update_lazy()] method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest]
+                                                                                            ]             [O(1)]            [O(log(N))]     [O(log(N))]  [O(1)]]
+
+    [[[classref boost::heap::pairing_heap]]         [[^O(1)]]   [O(2**2*log(log(N)))]   [O(log(N))] [O(2**2*log(log(N)))]   [O(2**2*log(log(N)))]  [O(2**2*log(log(N)))]    [O(2**2*log(log(N)))]   [O(2**2*log(log(N)))]]
+    [[[classref boost::heap::skew_heap]]            [[^O(1)]]   [O(log(N))]     [O(log(N))]  [O(log(N))]   [O(log(N))]       [O(log(N))]     [O(log(N))]    [O(log(N+M))]]
+]
+
+
+
+[section Data Structure Configuration]
+
+The data structures can be configured with [@boost:/libs/parameter/doc/html/index.html Boost.Parameter]-style templates.
+
+[variablelist
+    [[[classref boost::heap::compare]]
+     [Predicate for defining the heap order, optional
+      (defaults to =boost::heap::compare<std::less<T> >=)]
+    ]
+    [[[classref boost::heap::allocator]]
+     [Allocator for internal memory management, optional
+      (defaults to =boost::heap::allocator<std::allocator<T> >=)]
+    ]
+    [[[classref boost::heap::stable]]
+     [Configures the heap to use a [link heap.concepts.stability stable heap order], optional (defaults to =boost::heap::stable<false>=).
+     ]
+    ]
+    [[[classref boost::heap::mutable_]]
+     [Configures the heap to be mutable. [classref boost::heap::d_ary_heap] and [classref boost::heap::skew_heap] have to be configured
+      with this policy to enable the [link heap.concepts.mutability mutability interface].
+     ]
+    ]
+    [[[classref boost::heap::stability_counter_type]]
+     [Configures the integer type used for the stability counter, optional (defaults to =boost::heap::stability_counter_type<boost::uintmax_t>=).
+      For more details, consult the [link heap.concepts.stability Stability] section.
+     ]
+    ]
+    [[[classref boost::heap::constant_time_size]]
+     [Specifies, whether =size()= should have linear or constant complexity. This argument is only available for node-based
+      heap data structures and if available, it is optional (defaults to =boost::heap::constant_time_size<true>=)]
+    ]
+
+    [[[classref boost::heap::arity]]
+     [Specifies the arity of a d-ary heap. For details, please consult the class reference of [classref boost::heap::d_ary_heap]]
+    ]
+
+    [[[classref boost::heap::store_parent_pointer]]
+     [Store the parent pointer in the heap nodes. This policy is only available in the [classref boost::heap::skew_heap].
+     ]
+    ]
+]
+
+[endsect]
+
+[endsect]
+
+
+[xinclude autodoc.xml]
+
+
+[section Acknowledgements]
+
+[variablelist
+    [[Google Inc.]
+     [For sponsoring the development of this library during the Summer of Code 2010]
+    ]
+    [[Hartmut Kaiser]
+     [For mentoring the Summer of Code project]
+    ]
+]
+[endsect]
\ No newline at end of file
diff --git a/libs/heap/examples/interface.cpp b/libs/heap/examples/interface.cpp
new file mode 100644
index 0000000000..f46a20d498
--- /dev/null
+++ b/libs/heap/examples/interface.cpp
@@ -0,0 +1,261 @@
+/*=============================================================================
+    Copyright (c) 2010 Tim Blechmann
+
+    Use, modification and distribution is subject to the Boost Software
+    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+    http://www.boost.org/LICENSE_1_0.txt)
+=============================================================================*/
+
+#include <iostream>
+#include <iomanip>
+
+#include "../../../boost/heap/fibonacci_heap.hpp"
+
+using std::cout;
+using std::endl;
+using namespace boost::heap;
+
+//[ basic_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void basic_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    cout << "Priority Queue: popped elements" << endl;
+    cout << pq.top() << " "; // 3
+    pq.pop();
+    cout << pq.top() << " "; // 2
+    pq.pop();
+    cout << pq.top() << " "; // 1
+    pq.pop();
+    cout << endl;
+}
+//]
+
+//[ iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void iterator_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    typename PriorityQueue::iterator begin = pq.begin();
+    typename PriorityQueue::iterator end = pq.end();
+
+    cout << "Priority Queue: iteration" << endl;
+    for (typename PriorityQueue::iterator it = begin; it != end; ++it)
+        cout << *it << " "; // 1, 2, 3 in unspecified order
+    cout << endl;
+}
+//]
+
+//[ ordered_iterator_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void ordered_iterator_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(2);
+    pq.push(3);
+    pq.push(1);
+
+    typename PriorityQueue::ordered_iterator begin = pq.ordered_begin();
+    typename PriorityQueue::ordered_iterator end = pq.ordered_end();
+
+    cout << "Priority Queue: ordered iteration" << endl;
+    for (typename PriorityQueue::ordered_iterator it = begin; it != end; ++it)
+        cout << *it << " "; // 3, 2, 1 (i.e. 1, 2, 3 in heap order)
+    cout << endl;
+}
+//]
+
+
+//[ merge_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void merge_interface(void)
+{
+    PriorityQueue pq;
+
+    pq.push(3);
+    pq.push(5);
+    pq.push(1);
+
+    PriorityQueue pq2;
+
+    pq2.push(2);
+    pq2.push(4);
+    pq2.push(0);
+
+    pq.merge(pq2);
+
+    cout << "Priority Queue: merge" << endl;
+    cout << "first queue: ";
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 5 4 3 2 1 0
+        pq.pop();
+    }
+    cout << endl;
+
+    cout << "second queue: ";
+    while (!pq2.empty()) {
+        cout << pq2.top() << " "; // 4 2 0
+        pq2.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ heap_merge_algorithm
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void heap_merge_algorithm(void)
+{
+    PriorityQueue pq;
+
+    pq.push(3);
+    pq.push(5);
+    pq.push(1);
+
+    PriorityQueue pq2;
+
+    pq2.push(2);
+    pq2.push(4);
+    pq2.push(0);
+
+    boost::heap::heap_merge(pq, pq2);
+
+    cout << "Priority Queue: merge" << endl;
+    cout << "first queue: ";
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 5 4 3 2 1 0
+        pq.pop();
+    }
+    cout << endl;
+
+    cout << "second queue: ";
+    while (!pq2.empty()) {
+        cout << pq2.top() << " "; // 4 2 0
+        pq2.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_interface(void)
+{
+    PriorityQueue pq;
+    typedef typename PriorityQueue::handle_type handle_t;
+
+    handle_t t3 = pq.push(3);
+    handle_t t5 = pq.push(5);
+    handle_t t1 = pq.push(1);
+
+    pq.update(t3, 4);
+    pq.increase(t5, 7);
+    pq.decrease(t1, 0);
+
+    cout << "Priority Queue: update" << endl;
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 7, 4, 0
+        pq.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_fixup_interface
+// PriorityQueue is expected to be a max-heap of integer values
+template <typename PriorityQueue>
+void mutable_fixup_interface(void)
+{
+    PriorityQueue pq;
+    typedef typename PriorityQueue::handle_type handle_t;
+
+    handle_t t3 = pq.push(3);
+    handle_t t5 = pq.push(5);
+    handle_t t1 = pq.push(1);
+
+    *t3 = 4;
+    pq.update(t3);
+
+    *t5 = 7;
+    pq.increase(t5);
+
+    *t1 = 0;
+    pq.decrease(t1);
+
+    cout << "Priority Queue: update with fixup" << endl;
+    while (!pq.empty()) {
+        cout << pq.top() << " "; // 7, 4, 0
+        pq.pop();
+    }
+    cout << endl;
+}
+//]
+
+//[ mutable_interface_handle_in_value
+struct heap_data
+{
+    fibonacci_heap<heap_data>::handle_type handle;
+    int payload;
+
+    heap_data(int i):
+        payload(i)
+    {}
+
+    bool operator<(heap_data const & rhs) const
+    {
+        return payload < rhs.payload;
+    }
+};
+
+void mutable_interface_handle_in_value(void)
+{
+    fibonacci_heap<heap_data> heap;
+    heap_data f(2);
+
+    fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
+    (*handle).handle = handle; // store handle in node
+}
+//]
+
+
+int main(void)
+{
+    using boost::heap::fibonacci_heap;
+
+    cout << std::setw(2);
+
+    basic_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    iterator_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    ordered_iterator_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    merge_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    mutable_interface<fibonacci_heap<int> >();
+    cout << endl;
+
+    mutable_fixup_interface<fibonacci_heap<int> >();
+
+    mutable_interface_handle_in_value();
+}
\ No newline at end of file
diff --git a/libs/heap/index.html b/libs/heap/index.html
new file mode 100644
index 0000000000..2717f97112
--- /dev/null
+++ b/libs/heap/index.html
@@ -0,0 +1,13 @@
+<html>
+<head>
+<meta http-equiv="refresh" content="0; URL=../../doc/html/heap.html">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="../../doc/html/heap.html">../../doc/html/heap.html</a> &nbsp;<hr>
+<p>&copy; Copyright Beman Dawes, 2001</p>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying 
+file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy 
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>
diff --git a/libs/heap/test/Jamfile.v2 b/libs/heap/test/Jamfile.v2
new file mode 100644
index 0000000000..856ad5c919
--- /dev/null
+++ b/libs/heap/test/Jamfile.v2
@@ -0,0 +1,23 @@
+# (C) Copyright 2010: Tim Blechmann
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import testing ;
+
+rule test_all
+{
+   local all_rules = ;
+
+   for local fileb in [ glob *.cpp ]
+   {
+       all_rules += [ run $(fileb) ../../test/build//boost_unit_test_framework/<link>static
+      :  # additional args
+      :  # test-files
+      : <library>/boost/test//boost_unit_test_framework # requirements
+      ] ;
+   }
+
+    return $(all_rules) ;
+}
+
+test-suite heap : [ test_all r ] : <threading>multi ;
diff --git a/libs/heap/test/binomial_heap_test.cpp b/libs/heap/test/binomial_heap_test.cpp
new file mode 100644
index 0000000000..50c0e17009
--- /dev/null
+++ b/libs/heap/test/binomial_heap_test.cpp
@@ -0,0 +1,48 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/binomial_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_binomial_heap_test(void)
+{
+    typedef boost::heap::binomial_heap<int, boost::heap::stable<stable>,
+                                            boost::heap::compare<std::less<int> >,
+                                            boost::heap::allocator<std::allocator<int> >,
+                                            boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+    BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    run_mutable_heap_tests<pri_queue >();
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::binomial_heap<q_tester, boost::heap::stable<stable>,
+                                                     boost::heap::constant_time_size<constant_time_size> > stable_pri_queue;
+
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+BOOST_AUTO_TEST_CASE( binomial_heap_test )
+{
+    run_binomial_heap_test<false, false>();
+    run_binomial_heap_test<false, true>();
+    run_binomial_heap_test<true, false>();
+    run_binomial_heap_test<true, true>();
+}
diff --git a/libs/heap/test/common_heap_tests.hpp b/libs/heap/test/common_heap_tests.hpp
new file mode 100644
index 0000000000..191ab7f343
--- /dev/null
+++ b/libs/heap/test/common_heap_tests.hpp
@@ -0,0 +1,435 @@
+#ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
+#define COMMON_HEAP_TESTS_HPP_INCLUDED
+
+#include <algorithm>
+#include <vector>
+
+#include <boost/concept/assert.hpp>
+#include <boost/concept_archetype.hpp>
+
+#include <boost/heap/heap_concepts.hpp>
+
+
+typedef boost::default_constructible_archetype<
+        boost::less_than_comparable_archetype<
+        boost::copy_constructible_archetype<
+        boost::assignable_archetype<
+        > > > > test_value_type;
+
+
+typedef std::vector<int> test_data;
+const int test_size = 64;//128;
+
+struct dummy_run
+{
+    static void run(void)
+    {}
+};
+
+
+test_data make_test_data(int size, int offset = 0, int strive = 1)
+{
+    test_data ret;
+
+    for (int i = 0; i != size; ++i)
+        ret.push_back(i * strive + offset);
+    return ret;
+}
+
+
+template <typename pri_queue, typename data_container>
+void check_q(pri_queue & q, data_container const & expected)
+{
+    BOOST_REQUIRE_EQUAL(q.size(), expected.size());
+
+    for (unsigned int i = 0; i != expected.size(); ++i)
+    {
+        BOOST_REQUIRE_EQUAL(q.size(), expected.size() - i);
+        BOOST_REQUIRE_EQUAL(q.top(), expected[expected.size()-1-i]);
+        q.pop();
+    }
+
+    BOOST_REQUIRE(q.empty());
+}
+
+
+template <typename pri_queue, typename data_container>
+void fill_q(pri_queue & q, data_container const & data)
+{
+    for (unsigned int i = 0; i != data.size(); ++i)
+        q.push(data[i]);
+}
+
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+template <typename pri_queue, typename data_container>
+void fill_emplace_q(pri_queue & q, data_container const & data)
+{
+    for (unsigned int i = 0; i != data.size(); ++i) {
+        typename pri_queue::value_type value = data[i];
+        q.emplace(std::move(value));
+    }
+}
+#endif
+
+template <typename pri_queue>
+void pri_queue_test_sequential_push(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_sequential_reverse_push(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        std::reverse(data.begin(), data.end());
+        fill_q(q, data);
+        std::reverse(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_emplace(void)
+{
+#if defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        std::reverse(data.begin(), data.end());
+        fill_emplace_q(q, data);
+        std::reverse(data.begin(), data.end());
+        check_q(q, data);
+    }
+#endif
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_random_push(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+
+        test_data shuffled (data);
+        std::random_shuffle(shuffled.begin(), shuffled.end());
+
+        fill_q(q, shuffled);
+
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_copyconstructor(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+
+        pri_queue r(q);
+
+        check_q(r, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_assignment(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+
+        pri_queue r;
+        r = q;
+
+        check_q(r, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_moveconstructor(void)
+{
+#ifdef BOOST_HAS_RVALUE_REFS
+    pri_queue q;
+    test_data data = make_test_data(test_size);
+    fill_q(q, data);
+
+    pri_queue r(std::move(q));
+
+    check_q(r, data);
+    BOOST_REQUIRE(q.empty());
+#endif
+}
+
+template <typename pri_queue>
+void pri_queue_test_move_assignment(void)
+{
+#ifdef BOOST_HAS_RVALUE_REFS
+    pri_queue q;
+    test_data data = make_test_data(test_size);
+    fill_q(q, data);
+
+    pri_queue r;
+    r = std::move(q);
+
+    check_q(r, data);
+    BOOST_REQUIRE(q.empty());
+#endif
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_swap(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        test_data shuffled (data);
+        std::random_shuffle(shuffled.begin(), shuffled.end());
+        fill_q(q, shuffled);
+
+        pri_queue r;
+
+        q.swap(r);
+        check_q(r, data);
+        BOOST_REQUIRE(q.empty());
+    }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_iterators(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        test_data data = make_test_data(test_size);
+        test_data shuffled (data);
+        std::random_shuffle(shuffled.begin(), shuffled.end());
+        pri_queue q;
+        BOOST_REQUIRE(q.begin() == q.end());
+        fill_q(q, shuffled);
+
+        for (unsigned long i = 0; i != data.size(); ++i)
+            BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i]) != q.end());
+
+        for (unsigned long i = 0; i != data.size(); ++i)
+            BOOST_REQUIRE(std::find(q.begin(), q.end(), data[i] + data.size()) == q.end());
+
+        test_data data_from_queue(q.begin(), q.end());
+        std::sort(data_from_queue.begin(), data_from_queue.end());
+
+        BOOST_REQUIRE(data == data_from_queue);
+
+        for (unsigned long i = 0; i != data.size(); ++i) {
+            BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - i));
+            q.pop();
+        }
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_ordered_iterators(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        test_data data = make_test_data(i);
+        test_data shuffled (data);
+        std::random_shuffle(shuffled.begin(), shuffled.end());
+        pri_queue q;
+        BOOST_REQUIRE(q.ordered_begin() == q.ordered_end());
+        fill_q(q, shuffled);
+
+        test_data data_from_queue(q.ordered_begin(), q.ordered_end());
+        std::reverse(data_from_queue.begin(), data_from_queue.end());
+        BOOST_REQUIRE(data == data_from_queue);
+
+        for (unsigned long i = 0; i != data.size(); ++i)
+            BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i]) != q.ordered_end());
+
+        for (unsigned long i = 0; i != data.size(); ++i)
+            BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[i] + data.size()) == q.ordered_end());
+
+        for (unsigned long i = 0; i != data.size(); ++i) {
+            BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - i));
+            q.pop();
+        }
+    }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_equality(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+        std::reverse(data.begin(), data.end());
+        fill_q(r, data);
+
+        BOOST_REQUIRE(r == q);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_inequality(void)
+{
+    for (int i = 1; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+        data[0] = data.back() + 1;
+        fill_q(r, data);
+
+        BOOST_REQUIRE(r != q);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_less(void)
+{
+    for (int i = 1; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        test_data r_data(data);
+        r_data.pop_back();
+
+        fill_q(q, data);
+        fill_q(r, r_data);
+
+        BOOST_REQUIRE(r < q);
+    }
+
+    for (int i = 1; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        test_data r_data(data);
+        data.push_back(data.back() + 1);
+
+        fill_q(q, data);
+        fill_q(r, r_data);
+
+        BOOST_REQUIRE(r < q);
+    }
+
+    for (int i = 1; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        test_data r_data(data);
+
+        data.back() += 1;
+
+        fill_q(q, data);
+        fill_q(r, r_data);
+
+        BOOST_REQUIRE(r < q);
+    }
+
+    for (int i = 1; i != test_size; ++i)
+    {
+        pri_queue q, r;
+        test_data data = make_test_data(i);
+        test_data r_data(data);
+
+        r_data.front() -= 1;
+
+        fill_q(q, data);
+        fill_q(r, r_data);
+
+        BOOST_REQUIRE(r < q);
+    }
+
+}
+
+template <typename pri_queue>
+void pri_queue_test_clear(void)
+{
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(i);
+        fill_q(q, data);
+
+        q.clear();
+        BOOST_REQUIRE(q.size() == 0);
+        BOOST_REQUIRE(q.empty());
+    }
+}
+
+
+template <typename pri_queue>
+void run_concept_check(void)
+{
+    BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+}
+
+template <typename pri_queue>
+void run_common_heap_tests(void)
+{
+    pri_queue_test_sequential_push<pri_queue>();
+    pri_queue_test_sequential_reverse_push<pri_queue>();
+    pri_queue_test_random_push<pri_queue>();
+    pri_queue_test_equality<pri_queue>();
+    pri_queue_test_inequality<pri_queue>();
+    pri_queue_test_less<pri_queue>();
+    pri_queue_test_clear<pri_queue>();
+
+    pri_queue_test_emplace<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_iterator_heap_tests(void)
+{
+    pri_queue_test_iterators<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_copyable_heap_tests(void)
+{
+    pri_queue_test_copyconstructor <pri_queue>();
+    pri_queue_test_assignment<pri_queue>();
+    pri_queue_test_swap<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_moveable_heap_tests(void)
+{
+    pri_queue_test_moveconstructor <pri_queue>();
+    pri_queue_test_move_assignment <pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_reserve_heap_tests(void)
+{
+    test_data data = make_test_data(test_size);
+    pri_queue q;
+    q.reserve(6);
+    fill_q(q, data);
+
+    check_q(q, data);
+}
+
+#endif // COMMON_HEAP_TESTS_HPP_INCLUDED
diff --git a/libs/heap/test/d_ary_heap_test.cpp b/libs/heap/test/d_ary_heap_test.cpp
new file mode 100644
index 0000000000..18a4248888
--- /dev/null
+++ b/libs/heap/test/d_ary_heap_test.cpp
@@ -0,0 +1,102 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/d_ary_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <int D, bool stable>
+void run_d_ary_heap_test(void)
+{
+    typedef boost::heap::d_ary_heap<int, boost::heap::arity<D>,
+                                         boost::heap::stable<stable>,
+                                         boost::heap::compare<std::less<int> >,
+                                         boost::heap::allocator<std::allocator<int> > > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+    run_concept_check<pri_queue>();
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+    run_reserve_heap_tests<pri_queue>();
+    run_merge_tests<pri_queue>();
+
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::d_ary_heap<q_tester, boost::heap::arity<D>,
+                                                  boost::heap::stable<stable>
+                                       > stable_pri_queue;
+
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_test )
+{
+    run_d_ary_heap_test<2, false>();
+    run_d_ary_heap_test<3, false>();
+    run_d_ary_heap_test<4, false>();
+    run_d_ary_heap_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_stable_test )
+{
+    run_d_ary_heap_test<2, true>();
+    run_d_ary_heap_test<3, true>();
+    run_d_ary_heap_test<4, true>();
+    run_d_ary_heap_test<5, true>();
+}
+
+template <int D, bool stable>
+void run_d_ary_heap_mutable_test(void)
+{
+    typedef boost::heap::d_ary_heap<int, boost::heap::mutable_<true>,
+                                            boost::heap::arity<D>,
+                                            boost::heap::stable<stable>
+                                           > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+    run_reserve_heap_tests<pri_queue>();
+    run_mutable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::d_ary_heap<q_tester, boost::heap::mutable_<true>,
+                                                boost::heap::arity<D>,
+                                                boost::heap::stable<stable>
+                                               > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_test )
+{
+    run_d_ary_heap_mutable_test<2, false>();
+    run_d_ary_heap_mutable_test<3, false>();
+    run_d_ary_heap_mutable_test<4, false>();
+    run_d_ary_heap_mutable_test<5, false>();
+}
+
+BOOST_AUTO_TEST_CASE( d_ary_heap_mutable_stable_test )
+{
+    run_d_ary_heap_mutable_test<2, true>();
+    run_d_ary_heap_mutable_test<3, true>();
+    run_d_ary_heap_mutable_test<4, true>();
+    run_d_ary_heap_mutable_test<5, true>();
+}
diff --git a/libs/heap/test/fibonacci_heap_test.cpp b/libs/heap/test/fibonacci_heap_test.cpp
new file mode 100644
index 0000000000..7429a24a49
--- /dev/null
+++ b/libs/heap/test/fibonacci_heap_test.cpp
@@ -0,0 +1,51 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/fibonacci_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+
+template <bool stable, bool constant_time_size>
+void run_fibonacci_heap_test(void)
+{
+    typedef boost::heap::fibonacci_heap<int, boost::heap::stable<stable>,
+                                             boost::heap::compare<std::less<int> >,
+                                             boost::heap::allocator<std::allocator<int> >,
+                                             boost::heap::constant_time_size<constant_time_size>
+                                       > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+    BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    run_mutable_heap_tests<pri_queue>();
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::fibonacci_heap<q_tester, boost::heap::stable<stable>,
+                                            boost::heap::constant_time_size<constant_time_size>
+                                           > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_test )
+{
+    run_fibonacci_heap_test<true, false>();
+    run_fibonacci_heap_test<true, true>();
+
+    run_fibonacci_heap_test<false, false>();
+    run_fibonacci_heap_test<false, true>();
+}
diff --git a/libs/heap/test/merge_heap_tests.hpp b/libs/heap/test/merge_heap_tests.hpp
new file mode 100644
index 0000000000..c7b9f99834
--- /dev/null
+++ b/libs/heap/test/merge_heap_tests.hpp
@@ -0,0 +1,67 @@
+#include "common_heap_tests.hpp"
+#include <boost/heap/heap_merge.hpp>
+
+#define GENERATE_TEST_DATA(INDEX)                           \
+    test_data data = make_test_data(test_size, 0, 1);       \
+    std::random_shuffle(data.begin(), data.end());          \
+                                                            \
+    test_data data_q (data.begin(), data.begin() + INDEX);  \
+    test_data data_r (data.begin() + INDEX, data.end());    \
+                                                            \
+    std::stable_sort(data.begin(), data.end());
+
+
+template <typename pri_queue>
+struct pri_queue_test_merge
+{
+    static void run(void)
+    {
+        for (int i = 0; i != test_size; ++i) {
+            pri_queue q, r;
+            GENERATE_TEST_DATA(i);
+
+            fill_q(q, data_q);
+            fill_q(r, data_r);
+
+            q.merge(r);
+
+            BOOST_REQUIRE(r.empty());
+            check_q(q, data);
+        }
+    }
+};
+
+
+template <typename pri_queue1, typename pri_queue2>
+struct pri_queue_test_heap_merge
+{
+    static void run (void)
+    {
+        for (int i = 0; i != test_size; ++i) {
+            pri_queue1 q;
+            pri_queue2 r;
+            GENERATE_TEST_DATA(i);
+
+            fill_q(q, data_q);
+            fill_q(r, data_r);
+
+            boost::heap::heap_merge(q, r);
+
+            BOOST_REQUIRE(r.empty());
+            check_q(q, data);
+        }
+    }
+};
+
+
+
+template <typename pri_queue>
+void run_merge_tests(void)
+{
+    boost::mpl::if_c<pri_queue::is_mergable,
+                     pri_queue_test_merge<pri_queue>,
+                     dummy_run
+                    >::type::run();
+
+    pri_queue_test_heap_merge<pri_queue, pri_queue>::run();
+}
diff --git a/libs/heap/test/mutable_heap_test.cpp b/libs/heap/test/mutable_heap_test.cpp
new file mode 100644
index 0000000000..b7827fc7c8
--- /dev/null
+++ b/libs/heap/test/mutable_heap_test.cpp
@@ -0,0 +1,134 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <boost/heap/d_ary_heap.hpp>
+#include <boost/heap/fibonacci_heap.hpp>
+#include <boost/heap/pairing_heap.hpp>
+#include <boost/heap/binomial_heap.hpp>
+#include <boost/heap/skew_heap.hpp>
+
+using namespace boost::heap;
+
+
+typedef fibonacci_heap<struct fwd_declared_struct_1>::handle_type handle_type_1;
+typedef d_ary_heap<struct fwd_declared_struct_2, arity<4>, mutable_<true> >::handle_type handle_type_2;
+typedef pairing_heap<struct fwd_declared_struct_3>::handle_type handle_type_3;
+typedef binomial_heap<struct fwd_declared_struct_4>::handle_type handle_type_4;
+typedef skew_heap<struct fwd_declared_struct_5, mutable_<true> >::handle_type handle_type_5;
+
+template <typename HeapType>
+void run_handle_as_member_test(void)
+{
+    typedef typename HeapType::value_type value_type;
+    HeapType heap;
+    value_type f(2);
+    typename value_type::handle_type handle = heap.push(f);
+    value_type & fInHeap = *handle;
+    fInHeap.handle = handle;
+}
+
+
+struct fibonacci_heap_data
+{
+    typedef fibonacci_heap<fibonacci_heap_data>::handle_type handle_type;
+
+    handle_type handle;
+    int i;
+
+    fibonacci_heap_data(int i):i(i) {}
+
+    bool operator<(fibonacci_heap_data const & rhs) const
+    {
+        return i < rhs.i;
+    }
+};
+
+BOOST_AUTO_TEST_CASE( fibonacci_heap_handle_as_member )
+{
+    run_handle_as_member_test<fibonacci_heap<fibonacci_heap_data> >();
+}
+
+struct d_heap_data
+{
+    typedef d_ary_heap<d_heap_data, arity<4>, mutable_<true> >::handle_type handle_type;
+
+    handle_type handle;
+    int i;
+
+    d_heap_data(int i):i(i) {}
+
+    bool operator<(d_heap_data const & rhs) const
+    {
+        return i < rhs.i;
+    }
+};
+
+
+BOOST_AUTO_TEST_CASE( d_heap_handle_as_member )
+{
+    run_handle_as_member_test<d_ary_heap<d_heap_data, arity<4>, mutable_<true> > >();
+}
+
+struct pairing_heap_data
+{
+    typedef pairing_heap<pairing_heap_data>::handle_type handle_type;
+
+    handle_type handle;
+    int i;
+
+    pairing_heap_data(int i):i(i) {}
+
+    bool operator<(pairing_heap_data const & rhs) const
+    {
+        return i < rhs.i;
+    }
+};
+
+
+BOOST_AUTO_TEST_CASE( pairing_heap_handle_as_member )
+{
+    run_handle_as_member_test<pairing_heap<pairing_heap_data> >();
+}
+
+
+struct binomial_heap_data
+{
+    typedef binomial_heap<binomial_heap_data>::handle_type handle_type;
+
+    handle_type handle;
+    int i;
+
+    binomial_heap_data(int i):i(i) {}
+
+    bool operator<(binomial_heap_data const & rhs) const
+    {
+            return i < rhs.i;
+    }
+};
+
+
+BOOST_AUTO_TEST_CASE( binomial_heap_handle_as_member )
+{
+    run_handle_as_member_test<binomial_heap<binomial_heap_data> >();
+}
+
+struct skew_heap_data
+{
+    typedef skew_heap<skew_heap_data, mutable_<true> >::handle_type handle_type;
+
+    handle_type handle;
+    int i;
+
+    skew_heap_data(int i):i(i) {}
+
+    bool operator<(skew_heap_data const & rhs) const
+    {
+        return i < rhs.i;
+    }
+};
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_handle_as_member )
+{
+    run_handle_as_member_test<skew_heap<skew_heap_data, mutable_<true> > >();
+}
diff --git a/libs/heap/test/mutable_heap_tests.hpp b/libs/heap/test/mutable_heap_tests.hpp
new file mode 100644
index 0000000000..6cee60d4a9
--- /dev/null
+++ b/libs/heap/test/mutable_heap_tests.hpp
@@ -0,0 +1,303 @@
+// random uses boost.fusion, which clashes with boost.test
+//#define USE_BOOST_RANDOM
+
+#ifdef USE_BOOST_RANDOM
+#include <boost/random.hpp>
+#else
+#include <cstdlib>
+#endif
+
+#include "common_heap_tests.hpp"
+
+
+#define PUSH_WITH_HANDLES(HANDLES, Q, DATA)                 \
+    std::vector<typename pri_queue::handle_type> HANDLES;   \
+                                                            \
+    for (unsigned int k = 0; k != data.size(); ++k)         \
+        HANDLES.push_back(Q.push(DATA[k]));
+
+
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        *handles[i] = -1;
+        data[i] = -1;
+        q.update(handles[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_decrease_function(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = -1;
+        q.update(handles[i], -1);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_function_identity(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        q.update(handles[i], data[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_shuffled(void)
+{
+    pri_queue q;
+    test_data data = make_test_data(test_size);
+    PUSH_WITH_HANDLES(handles, q, data);
+
+    test_data shuffled (data);
+    std::random_shuffle(shuffled.begin(), shuffled.end());
+
+    for (int i = 0; i != test_size; ++i)
+        q.update(handles[i], shuffled[i]);
+
+    check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_update_increase(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = data.back()+1;
+        *handles[i] = data[i];
+        q.update(handles[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_update_increase_function(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = data.back()+1;
+        q.update(handles[i], data[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        *handles[i] = -1;
+        data[i] = -1;
+        q.decrease(handles[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = -1;
+        q.decrease(handles[i], -1);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_decrease_function_identity(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        q.decrease(handles[i], data[i]);
+
+        check_q(q, data);
+    }
+}
+
+
+template <typename pri_queue>
+void pri_queue_test_increase(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = data.back()+1;
+        *handles[i] = data[i];
+        q.increase(handles[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        data[i] = data.back()+1;
+        q.increase(handles[i], data[i]);
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_increase_function_identity(void)
+{
+    for (int i = 0; i != test_size; ++i) {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        q.increase(handles[i], data[i]);
+
+        check_q(q, data);
+    }
+}
+
+template <typename pri_queue>
+void pri_queue_test_erase(void)
+{
+#ifdef USE_BOOST_RANDOM
+	boost::mt19937 rng;
+#endif
+
+    for (int i = 0; i != test_size; ++i)
+    {
+        pri_queue q;
+        test_data data = make_test_data(test_size);
+        PUSH_WITH_HANDLES(handles, q, data);
+
+        for (int j = 0; j != i; ++j)
+        {
+#ifdef USE_BOOST_RANDOM
+			boost::uniform_int<> range(0, data.size() - 1);
+			boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
+
+			int index = gen();
+#else
+            int index = rand() % (data.size() - 1);
+#endif
+            q.erase(handles[index]);
+            handles.erase(handles.begin() + index);
+            data.erase(data.begin() + index);
+        }
+
+        std::sort(data.begin(), data.end());
+        check_q(q, data);
+    }
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_update_tests(void)
+{
+    pri_queue_test_update_increase<pri_queue>();
+    pri_queue_test_update_decrease<pri_queue>();
+
+    pri_queue_test_update_shuffled<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_update_function_tests(void)
+{
+    pri_queue_test_update_increase_function<pri_queue>();
+    pri_queue_test_update_decrease_function<pri_queue>();
+    pri_queue_test_update_function_identity<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_decrease_tests(void)
+{
+    pri_queue_test_decrease<pri_queue>();
+    pri_queue_test_decrease_function<pri_queue>();
+    pri_queue_test_decrease_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_increase_tests(void)
+{
+    pri_queue_test_increase<pri_queue>();
+    pri_queue_test_increase_function<pri_queue>();
+    pri_queue_test_increase_function_identity<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_mutable_heap_erase_tests(void)
+{
+    pri_queue_test_erase<pri_queue>();
+}
+
+
+template <typename pri_queue>
+void run_mutable_heap_tests(void)
+{
+    run_mutable_heap_update_function_tests<pri_queue>();
+    run_mutable_heap_update_tests<pri_queue>();
+    run_mutable_heap_decrease_tests<pri_queue>();
+    run_mutable_heap_increase_tests<pri_queue>();
+    run_mutable_heap_erase_tests<pri_queue>();
+}
+
+template <typename pri_queue>
+void run_ordered_iterator_tests()
+{
+    pri_queue_test_ordered_iterators<pri_queue>();
+}
diff --git a/libs/heap/test/pairing_heap_tests.cpp b/libs/heap/test/pairing_heap_tests.cpp
new file mode 100644
index 0000000000..bb7132d0df
--- /dev/null
+++ b/libs/heap/test/pairing_heap_tests.cpp
@@ -0,0 +1,49 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/pairing_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size>
+void run_pairing_heap_test(void)
+{
+    typedef boost::heap::pairing_heap<int, boost::heap::stable<stable>,
+                                           boost::heap::compare<std::less<int> >,
+                                           boost::heap::allocator<std::allocator<int> >,
+                                           boost::heap::constant_time_size<constant_time_size> > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+    BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    run_mutable_heap_tests<pri_queue >();
+
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::pairing_heap<q_tester, boost::heap::stable<stable>,
+                                          boost::heap::constant_time_size<constant_time_size>
+                                         > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+BOOST_AUTO_TEST_CASE( pairing_heap_test )
+{
+    run_pairing_heap_test<false, false>();
+    run_pairing_heap_test<false, true>();
+    run_pairing_heap_test<true, false>();
+    run_pairing_heap_test<true, true>();
+}
diff --git a/libs/heap/test/priority_queue_test.cpp b/libs/heap/test/priority_queue_test.cpp
new file mode 100644
index 0000000000..9ad51421cc
--- /dev/null
+++ b/libs/heap/test/priority_queue_test.cpp
@@ -0,0 +1,35 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/priority_queue.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable>
+void run_common_priority_queue_tests(void)
+{
+    typedef boost::heap::priority_queue<int, boost::heap::stable<stable> > pri_queue;
+    BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+
+    run_concept_check<pri_queue>();
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+    run_merge_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::priority_queue<q_tester, boost::heap::stable<stable> > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+BOOST_AUTO_TEST_CASE( std_pri_queue_test )
+{
+    run_common_priority_queue_tests<false>();
+    run_common_priority_queue_tests<true>();
+}
diff --git a/libs/heap/test/skew_heap_test.cpp b/libs/heap/test/skew_heap_test.cpp
new file mode 100644
index 0000000000..fb79381bb0
--- /dev/null
+++ b/libs/heap/test/skew_heap_test.cpp
@@ -0,0 +1,95 @@
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+#include <algorithm>
+
+#include <boost/heap/skew_heap.hpp>
+
+#include "common_heap_tests.hpp"
+#include "stable_heap_tests.hpp"
+#include "mutable_heap_tests.hpp"
+#include "merge_heap_tests.hpp"
+
+template <bool stable, bool constant_time_size, bool store_parent_pointer>
+void run_skew_heap_test(void)
+{
+    typedef boost::heap::skew_heap<int, boost::heap::stable<stable>,
+                                        boost::heap::compare<std::less<int> >,
+                                        boost::heap::allocator<std::allocator<int> >,
+                                        boost::heap::constant_time_size<constant_time_size>,
+                                        boost::heap::store_parent_pointer<store_parent_pointer>
+                                  > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
+    BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    pri_queue_test_ordered_iterators<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>,
+                                       boost::heap::constant_time_size<constant_time_size>,
+                                       boost::heap::store_parent_pointer<store_parent_pointer>
+                                      > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+template <bool stable, bool constant_time_size>
+void run_skew_heap_mutable_test(void)
+{
+    typedef boost::heap::skew_heap<int, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+                                   boost::heap::compare<std::less<int> >,
+                                   boost::heap::allocator<std::allocator<int> >,
+                                   boost::heap::constant_time_size<constant_time_size>
+                                  > pri_queue;
+
+    BOOST_CONCEPT_ASSERT((boost::heap::MutablePriorityQueue<pri_queue>));
+    BOOST_CONCEPT_ASSERT((boost::heap::MergablePriorityQueue<pri_queue>));
+
+    run_common_heap_tests<pri_queue>();
+    run_iterator_heap_tests<pri_queue>();
+    run_copyable_heap_tests<pri_queue>();
+    run_moveable_heap_tests<pri_queue>();
+
+    run_merge_tests<pri_queue>();
+
+    run_mutable_heap_tests<pri_queue >();
+
+    run_ordered_iterator_tests<pri_queue>();
+
+    if (stable) {
+        typedef boost::heap::skew_heap<q_tester, boost::heap::stable<stable>, boost::heap::mutable_<true>,
+                                               boost::heap::constant_time_size<constant_time_size>
+                                              > stable_pri_queue;
+        run_stable_heap_tests<stable_pri_queue>();
+    }
+}
+
+
+BOOST_AUTO_TEST_CASE( skew_heap_test )
+{
+    run_skew_heap_test<false, false, true>();
+    run_skew_heap_test<false, true, true>();
+    run_skew_heap_test<true, false, true>();
+    run_skew_heap_test<true, true, true>();
+
+    run_skew_heap_test<false, false, false>();
+    run_skew_heap_test<false, true, false>();
+    run_skew_heap_test<true, false, false>();
+    run_skew_heap_test<true, true, false>();
+}
+
+BOOST_AUTO_TEST_CASE( skew_heap_mutable_test )
+{
+    run_skew_heap_mutable_test<false, false>();
+    run_skew_heap_mutable_test<false, true>();
+    run_skew_heap_mutable_test<true, false>();
+    run_skew_heap_mutable_test<true, true>();
+}
diff --git a/libs/heap/test/stable_heap_tests.hpp b/libs/heap/test/stable_heap_tests.hpp
new file mode 100644
index 0000000000..4455b9251d
--- /dev/null
+++ b/libs/heap/test/stable_heap_tests.hpp
@@ -0,0 +1,91 @@
+#include <boost/foreach.hpp>
+#include "common_heap_tests.hpp"
+
+struct q_tester
+{
+    q_tester(int i = 0, int j = 0):
+        value(i), id(j)
+    {}
+
+    bool operator< (q_tester const & rhs) const
+    {
+        return value < rhs.value;
+    }
+
+    bool operator> (q_tester const & rhs) const
+    {
+        return value > rhs.value;
+    }
+
+    bool operator== (q_tester const & rhs) const
+    {
+        return (value == rhs.value) && (id == rhs.id);
+    }
+
+    int value;
+    int id;
+};
+
+std::ostream& operator<< (std::ostream& out, q_tester const & t)
+{
+    out << "[" << t.value << " " << t.id << "]";
+    return out;
+}
+
+typedef std::vector<q_tester> stable_test_data;
+
+stable_test_data make_stable_test_data(int size, int same_count = 3,
+                                       int offset = 0, int strive = 1)
+{
+    stable_test_data ret;
+
+    for (int i = 0; i != size; ++i)
+        for (int j = 0; j != same_count; ++j)
+            ret.push_back(q_tester(i * strive + offset, j));
+    return ret;
+}
+
+struct compare_by_id
+{
+    bool operator()(q_tester const & lhs, q_tester const & rhs)
+    {
+        return lhs.id > rhs.id;
+    }
+};
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_push(void)
+{
+    stable_test_data data = make_stable_test_data(test_size);
+
+    pri_queue q;
+    fill_q(q, data);
+    std::stable_sort(data.begin(), data.end(), compare_by_id());
+    std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
+    check_q(q, data);
+}
+
+template <typename pri_queue>
+void pri_queue_stable_test_sequential_reverse_push(void)
+{
+    stable_test_data data = make_stable_test_data(test_size);
+    pri_queue q;
+    stable_test_data push_data(data);
+
+    std::stable_sort(push_data.begin(), push_data.end(), std::greater<q_tester>());
+
+    fill_q(q, push_data);
+
+    std::stable_sort(data.begin(), data.end(), compare_by_id());
+    std::stable_sort(data.begin(), data.end(), std::less<q_tester>());
+
+    check_q(q, data);
+}
+
+
+template <typename pri_queue>
+void run_stable_heap_tests(void)
+{
+    pri_queue_stable_test_sequential_push<pri_queue>();
+    pri_queue_stable_test_sequential_reverse_push<pri_queue>();
+}
diff --git a/libs/heap/tools/heap_benchmarks.hpp b/libs/heap/tools/heap_benchmarks.hpp
new file mode 100644
index 0000000000..5e1d1bbd3f
--- /dev/null
+++ b/libs/heap/tools/heap_benchmarks.hpp
@@ -0,0 +1,269 @@
+#include <algorithm>
+#include <vector>
+
+#include <boost/foreach.hpp>
+#include "high_resolution_timer.hpp"
+
+#include <boost/heap/heap_merge.hpp>
+
+#if defined(__GNUC__) && (!defined __INTEL_COMPILER)
+#define no_inline __attribute__ ((noinline))
+#else
+#define no_inline
+#endif
+
+typedef std::vector<int> test_data;
+
+const int num_benchmarks = 1;
+
+inline test_data make_sequential_test_data(int size)
+{
+    test_data v(size);
+    for (int i = 0; i != size; ++i)
+        v[i] = i;
+    return v;
+}
+
+inline test_data make_test_data(int size)
+{
+    test_data v = make_sequential_test_data(size);
+    std::random_shuffle(v.begin(), v.end());
+    return v;
+}
+
+const int max_data = 20;
+
+test_data const & get_data(int index)
+{
+    static std::vector <test_data> data;
+    if (data.empty())
+        for (int i = 0; i != num_benchmarks; ++i)
+            data.push_back(make_test_data((1<<(max_data+1))+1024));
+
+    return data[index];
+}
+
+
+#define DEFINE_BENCHMARKS_SELECTOR(SUFFIX)  \
+struct make_##SUFFIX                        \
+{                                           \
+    template <typename heap>                \
+    struct rebind {                         \
+        typedef run_##SUFFIX<heap> type;    \
+    };                                      \
+};
+
+
+template <typename pri_queue>
+void fill_heap(pri_queue & q, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        q.push(data[i]);
+        int top = q.top();
+        q.pop();
+        q.push(top);
+    }
+}
+
+template <typename pri_queue,
+          typename handle_container
+         >
+void fill_heap_with_handles(pri_queue & q, handle_container & handles, int index, int size, int offset = 0)
+{
+    test_data const & data = get_data(index);
+
+    for (int i = 0; i != size + 1; ++i) {
+        handles[i] = q.push(data[i]);
+
+        if (i > 0) {
+            typename pri_queue::handle_type last = handles[i-1];
+            int val = *last;
+            q.erase(last);
+            handles[i-1] = q.push(val);
+        }
+    }
+}
+
+
+template <typename pri_queue>
+struct run_sequential_push
+{
+    run_sequential_push(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+
+        for (int i = 0; i != 16; ++i)
+            q.push(data[(1<<max_data) + i]);
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_push)
+
+template <typename pri_queue>
+struct run_sequential_pop
+{
+    run_sequential_pop(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap(q, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        for (int i = 0; i != 16; ++i)
+            q.pop();
+    }
+
+    pri_queue q;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_pop)
+
+template <typename pri_queue>
+struct run_sequential_increase
+{
+    run_sequential_increase(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.increase(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_increase)
+
+template <typename pri_queue>
+struct run_sequential_decrease
+{
+    run_sequential_decrease(int size):
+        size(size), handles(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        fill_heap_with_handles(q, handles, index, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        test_data const & data = get_data(index);
+        for (int i = 0; i != 16; ++i)
+            q.decrease(handles[i], data[i] + (1<<max_data));
+    }
+
+    pri_queue q;
+    int size;
+    std::vector<typename pri_queue::handle_type> handles;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(sequential_decrease)
+
+template <typename pri_queue>
+struct run_merge_and_clear
+{
+    run_merge_and_clear(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+    }
+
+    no_inline void operator()(int index)
+    {
+        boost::heap::heap_merge(q, r);
+    }
+
+    pri_queue q, r;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(merge_and_clear)
+
+template <typename pri_queue>
+struct run_equivalence
+{
+    run_equivalence(int size):
+        size(size)
+    {}
+
+    void prepare(int index)
+    {
+        q.clear();
+        r.clear();
+        s.clear();
+
+        fill_heap(q, index, size);
+        fill_heap(r, index, size, size);
+        fill_heap(s, index, size);
+    }
+
+    no_inline bool operator()(int index)
+    {
+        return (q == r) ^ (q == s);
+    }
+
+    pri_queue q, r, s;
+    int size;
+};
+
+DEFINE_BENCHMARKS_SELECTOR(equivalence)
+
+
+template <typename benchmark>
+inline double run_benchmark(benchmark & b)
+{
+    boost::high_resolution_timer timer;
+    std::vector<double> results;
+
+    for (int i = 0; i != num_benchmarks; ++i)
+    {
+        b.prepare(i);
+        timer.restart();
+        b(i);
+        double t = timer.elapsed();
+        results.push_back(t);
+    }
+
+    return results.at(results.size()/2); // median
+}
diff --git a/libs/heap/tools/high_resolution_timer.hpp b/libs/heap/tools/high_resolution_timer.hpp
new file mode 100644
index 0000000000..9893b24413
--- /dev/null
+++ b/libs/heap/tools/high_resolution_timer.hpp
@@ -0,0 +1,208 @@
+/*=============================================================================
+    Copyright (c) 2005-2007 Hartmut Kaiser
+                  2007, 2009 Tim Blechmann
+
+    Distributed under the Boost Software License, Version 1.0.
+    (See accompanying file LICENSE_1_0.txt or copy at
+    http://www.boost.org/LICENSE_1_0.txt)
+=============================================================================*/
+#if !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+#define BOOST_HIGH_RESOLUTION_TIMER_HPP
+
+#include <boost/config.hpp>
+#include <boost/throw_exception.hpp>
+
+#if _POSIX_C_SOURCE >= 199309L
+
+#include "time.h"
+
+#include <stdexcept>
+#include <limits>
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        restart();
+    }
+
+    void restart()
+    {
+        int status = clock_gettime(CLOCK_REALTIME, &start_time);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        struct timespec now;
+
+        int status = clock_gettime(CLOCK_REALTIME, &now);
+
+        if (status == -1)
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        struct timespec diff;
+
+        double ret_sec = double(now.tv_sec - start_time.tv_sec);
+        double ret_nsec = double(now.tv_nsec - start_time.tv_nsec);
+
+        while (ret_nsec < 0)
+        {
+            ret_sec -= 1.0;
+            ret_nsec += 1e9;
+        }
+
+        double ret = ret_sec + ret_nsec / 1e9;
+
+        return ret;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    struct timespec start_time;
+};
+
+} // namespace boost
+
+#elif defined(__APPLE__)
+
+#import <mach/mach_time.h>
+
+
+namespace boost {
+
+class high_resolution_timer
+{
+public:
+    high_resolution_timer(void)
+    {
+        mach_timebase_info_data_t info;
+
+        kern_return_t err = mach_timebase_info(&info);
+        if (err)
+            throw std::runtime_error("cannot create mach timebase info");
+
+        conversion_factor = (double)info.numer/(double)info.denom;
+        restart();
+    }
+
+    void restart()
+    {
+        start = mach_absolute_time();
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        uint64_t now = mach_absolute_time();
+        double duration = double(now - start) * conversion_factor;
+
+        return duration
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return double((std::numeric_limits<double>::max)());
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 0.0;
+    }
+
+private:
+    uint64_t start;
+    double conversion_factor;
+};
+
+} // namespace boost
+
+#elif defined(BOOST_WINDOWS)
+
+#include <stdexcept>
+#include <limits>
+#include <windows.h>
+
+namespace boost {
+
+///////////////////////////////////////////////////////////////////////////////
+//
+//  high_resolution_timer
+//      A timer object measures elapsed time.
+//      CAUTION: Windows only!
+//
+///////////////////////////////////////////////////////////////////////////////
+class high_resolution_timer
+{
+public:
+    high_resolution_timer()
+    {
+        start_time.QuadPart = 0;
+        frequency.QuadPart = 0;
+
+        if (!QueryPerformanceFrequency(&frequency))
+            boost::throw_exception(std::runtime_error("Couldn't acquire frequency"));
+
+        restart();
+    }
+
+    void restart()
+    {
+        if (!QueryPerformanceCounter(&start_time))
+            boost::throw_exception(std::runtime_error("Couldn't initialize start_time"));
+    }
+
+    double elapsed() const                  // return elapsed time in seconds
+    {
+        LARGE_INTEGER now;
+        if (!QueryPerformanceCounter(&now))
+            boost::throw_exception(std::runtime_error("Couldn't get current time"));
+
+        return double(now.QuadPart - start_time.QuadPart) / frequency.QuadPart;
+    }
+
+    double elapsed_max() const   // return estimated maximum value for elapsed()
+    {
+        return (double((std::numeric_limits<LONGLONG>::max)())
+            - double(start_time.QuadPart)) / double(frequency.QuadPart);
+    }
+
+    double elapsed_min() const            // return minimum value for elapsed()
+    {
+        return 1.0 / frequency.QuadPart;
+    }
+
+private:
+    LARGE_INTEGER start_time;
+    LARGE_INTEGER frequency;
+};
+
+} // namespace boost
+
+#else
+
+//  For other platforms, simply fall back to boost::timer
+#include <boost/timer.hpp>
+#include <boost/throw_exception.hpp>
+
+namespace boost {
+    typedef boost::timer high_resolution_timer;
+}
+
+#endif
+
+#endif  // !defined(BOOST_HIGH_RESOLUTION_TIMER_HPP)
+
diff --git a/libs/heap/tools/throughput_benchmarks.cpp b/libs/heap/tools/throughput_benchmarks.cpp
new file mode 100644
index 0000000000..74c440a01b
--- /dev/null
+++ b/libs/heap/tools/throughput_benchmarks.cpp
@@ -0,0 +1,240 @@
+#include <iostream>
+#include <iomanip>
+
+
+#include "../../../boost/heap/d_ary_heap.hpp"
+#include "../../../boost/heap/pairing_heap.hpp"
+#include "../../../boost/heap/fibonacci_heap.hpp"
+#include "../../../boost/heap/binomial_heap.hpp"
+#include "../../../boost/heap/skew_heap.hpp"
+
+#include "heap_benchmarks.hpp"
+
+using namespace std;
+
+template <typename benchmark_selector>
+void run_benchmarks_immutable(void)
+{
+    for (int i = 4; i != max_data; ++i) {
+        for (int j = 0; j != 8; ++j) {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+template <typename benchmark_selector>
+void run_benchmarks_mutable(void)
+{
+    for (int i = 4; i != max_data; ++i)
+    {
+        for (int j = 0; j != 8; ++j)
+        {
+            int size = 1<<i;
+            if (j%4 == 1)
+                size += 1<<(i-3);
+            if (j%4 == 2)
+                size += 1<<(i-2);
+            if (j%4 == 3)
+                size += (1<<(i-3)) + (1<<(i-2));
+            if (j >= 4)
+                size += (1<<(i-1));
+
+            cout << size << "\t";
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<2>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<4>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::d_ary_heap<long, boost::heap::arity<8>, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::binomial_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::fibonacci_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::pairing_heap<long> >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+
+            {
+                typedef typename benchmark_selector::
+                    template rebind<boost::heap::skew_heap<long, boost::heap::mutable_<true> > >
+                    ::type benchmark_functor;
+                benchmark_functor benchmark(size);
+                double result = run_benchmark(benchmark);
+                cout << result << '\t';
+            }
+            cout << endl;
+        }
+    }
+}
+
+int main()
+{
+    cout << fixed << setprecision(12);
+
+    cout << "sequential push" << endl;
+    run_benchmarks_immutable<make_sequential_push>();
+
+    cout << endl << "sequential pop" << endl;
+    run_benchmarks_immutable<make_sequential_pop>();
+
+    cout << endl << "sequential increase" << endl;
+    run_benchmarks_mutable<make_sequential_increase>();
+
+    cout << endl << "sequential decrease" << endl;
+    run_benchmarks_mutable<make_sequential_decrease>();
+
+    cout << endl << "merge_and_clear" << endl;
+    run_benchmarks_immutable<make_merge_and_clear>();
+
+    cout << endl << "equivalence" << endl;
+    run_benchmarks_immutable<make_equivalence>();
+}