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

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 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
};

Example

// 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;
}

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

Example

// 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;
}

// 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)).

Mergable Priority Queues

Synopsis

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.

Example

// 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 Algorithms

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.

Example

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

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.

Example

// 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
}

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.

Example

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