Concepts & Interface

| Home | Libraries | People | FAQ | More

## Concepts & Interface

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

### Priority Queue Iterators

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

#### Ordered Iterators

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

###### Example

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

### Comparing Priority Queues & Equivalence

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

### Merging Priority Queues

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

### Mutability

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!

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