Приоритетными являются очереди объектов, которые упорядочены по их приоритету. Они поддерживают операции добавления узлов в структуру данных, доступа к верхнему элементу (элементу с наивысшим приоритетом) и удаления верхнего элемента.

	Note
	<boost.heap>реализует приоритетные очереди как максимальные кучи, чтобы соответствовать функциям кучи STL. Это контрастирует с типичным дизайном учебника, в котором используются мини-куски.

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

Приоритетные очереди обеспечивают итераторы, которые можно использовать для прохождения их элементов. Все итераторы кучи являются const_iterators, что означает, что они не могут быть использованы для изменения значений, потому что изменение значения узла кучи может повредить порядок кучи. Подробности модификации кучных узлов описаны в разделе об интерфейсемутабельности.

Итераторы не посещают кучу элементов в определенном порядке. Если не указано иное, все функции неконст-члена кучи аннулируют итераторы, в то время как все функции конст-члена сохраняют валидность итератора.

	Note
	Некоторые реализации требуют итераторов, которые содержат набор элементов, которые являются.открыл, но не посетил. Поэтому итераторы копирования могут быть неэффективными и их следует избегать.

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

Структуры данных<boost.heap>можно сравнить со стандартными операторами сравнения. Сравнение выполняется путем сравнения двух куч элементов с помощью элемента<value_compare>.

	Note
	В зависимости от типа кучи, эта операция может быть довольно дорогой, потому что обе структуры данных должны быть пройдены в кучном порядке. На кучах без заказанных итераторов кучу нужно копировать внутренне. Типичная сложность - 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;
}

Некоторые приоритетные очереди<boost.heap>являются изменчивыми, что означает, что приоритет их элементов может быть изменен. Для достижения изменчивости<boost.heap>вводится понятиеручек, которые могут использоваться для доступа к внутренним узлам очереди приоритета с целью изменения его значения и восстановления кучного порядка.

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
	Неправильное использование<increase>или<decrease>может привести к повреждению структуры данных приоритетной очереди. При ненадежном использовании<update>можно использовать за счет эффективности.

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

Обратите внимание, что ручки могут храниться внутри<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

Существует два различных API для поддержки мутабельности. Первое семейство функций обеспечивает обновление функциональности путем изменения текущего элемента путем присвоения нового значения. Второе семейство функций может быть использовано для фиксации структуры данных после того, как элемент был изменен непосредственно через ручку. В то время как это дает пользователю возможность изменить приоритет элементов очереди без необходимости изменения их неприоритетной части, с этим нужно обращаться осторожно. Кучу нужно закрепить сразу после изменения приоритета элемента.

Помимо функции<update>, предусмотрены две дополнительные функции<increase>и<decrease>, которые, как правило, более эффективны, чем общая функция<update>. Однако пользователь гарантирует, что приоритет элемента будет изменен в правильном направлении.

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

Итераторы могут быть закрыты для ручек с использованием функции статического элемента<s_handle_from_iterator>. Однако большинство реализаций<update>аннулируют все итераторы. Наиболее заметным исключением является<fibonacci heap>, предоставляющий ленивую функцию обновления, которая просто отменяет итераторы, которые связаны с этой ручкой.

	Warning
	После изменения приоритета с помощью ручки кучу нужно исправить, позвонив в одну из функций обновления. В противном случае структура приоритетной очереди может быть повреждена.

Очередь приоритетов является "стабильной", если элементы с таким же приоритетом выскакивают из кучи в том же порядке, в каком они вставлены. Структуры данных, предоставленные<boost.heap>, могут быть сконфигурированы таким образом, чтобы быть стабильными во время компиляции с использованием политики<boost::heap::stable>. Поддерживаются два понятия стабильности. Если куча сконфигурирована сотсутствием стабильности, порядок узлов того же приоритета не определен, если он сконфигурирован какстабильный, узлы того же приоритета упорядочены по времени их вставки.

Стабильность достигается путем связывания целого числа версий с каждым значением для того, чтобы различать значения с одним и тем же узлом. Тип этой версии считается по умолчанию<boost::uintmax_t>, что составляет по меньшей мере 64 бита на большинстве систем. Однако он может быть настроен на использование другого типа с использованием аргумента шаблона<boost::heap::stability_counter_type>.

Warning

Счетчик стабильности склонен к целочисленным переполнениям. Если во время вызова<push()>произойдет переполнение, операция выйдет из строя и будет брошено исключение. Позже<push()>звонок будет успешным, но стабильный куча порядка будет скомпрометирована. Однако переполнение целых чисел на 64-битной частоте очень маловероятно: если приложение выдаст одну<push()>операцию в микросекунду, значение будет переполнено более чем через 500 000 лет.