...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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 | |
---|---|
|
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 ordered iterators static const bool is_mergable; // priority queue is efficiently mergable static const bool is_stable; // priority queue has a stable heap order static const bool has_reserve; // priority queue has a reserve() member };
// 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; }
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 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. |
// 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; }
Except for boost::heap::priority_queue
all boost.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)).
// 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; }
The data structures of boost.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)). |
class mergable_heap_interface { public: // public member functions void merge(mergable_heap_interface &); };
boost.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.
// 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; }
boost.heap
provides a heap_merge()
algorithm that is can be used to merge different kinds of heaps. Using this
algorithm, all boost.heap
data structures can be merged,
although some cannot be merged efficiently.
// 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; }
Some priority queues of boost.heap
are mutable, that means
the priority of their elements can be changed. To achieve mutability, boost.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.
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 |
// 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; }
Note that handles can be stored inside the value_type
:
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 }
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.
// 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; }
Iterators can be converted 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 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! |
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 boost.heap
, can be configured to be stable
at compile time using the 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 boost::heap::stability_counter_type
template argument.
Warning | |
---|---|
The stability counter is prone to integer overflows. If an overflow occurs
during a |