Когда следует использовать make_heap и Priority Queue?

Ответ 1

Нет никакой разницы в характеристиках производительности. std::priority_queue - это просто класс адаптера, который обертывает контейнер и те же вызовы функций, связанных с кучей, в класс. В спецификации std::priority_queue открыто указано, что.

Создавая очередь приоритетов с кучей из открытого std::vector (путем непосредственного вызова функций, связанных с кучей), вы держите его открытым для возможности внешнего доступа, что может повредить целостность кучи/очереди. std::priority_queue действует как барьер, ограничивающий доступ к "каноническому" минимуму: push(), pop(), top() и т.д. Вы можете видеть это как меру обеспечения самодисциплины.

Кроме того, адаптируя свой интерфейс очереди к "каноническому" набору операций, вы делаете его единообразным и взаимозаменяемым с другими реализациями очередей приоритетов на основе классов, которые соответствуют той же внешней спецификации.

Ответ 2

A priority_queue (по крайней мере, обычно) реализуется как куча. Таким образом, реальный вопрос заключается в том, предоставляет ли priority_queue то, что вам нужно. Когда вы используете make_heap, у вас все еще есть доступ ко всем элементам. Когда вы используете priority_queue, у вас есть только несколько операций, дающих очень ограниченный доступ к элементам (в основном просто вставляем элемент и удаляем элемент в начале очереди).

Ответ 3

priority_queue не является контейнером. Это адаптер контейнера, который использует конкретный базовый контейнер, например. vector или deque и предоставляет определенный набор методов для работы с данными. Более того, его реализация основана на алгоритмах *_heap.

Например, всякий раз, когда вы нажимаете новое значение на vector, вы должны вызвать push_heap, чтобы расширить диапазон, рассматриваемый как куча. Если вы не используете priority_queue, это позволяет рассматривать, скажем, половину vector как кучу (std::make_heap(v.begin(), v.begin() + (v.size() / 2))), тогда как другая половина будет как-есть.

Что priority_queue делает, когда вы вызываете push на нем: он подталкивает новый элемент к задней части базового контейнера и вызывает push_heap, чтобы сохранить свойство кучи приоритетным (это имеет значение только для того, чтобы первый элемент был наибольшим).

Я бы сказал, что лучше рассмотреть дизайн решения и ваши конкретные требования, а не проблемы с производительностью.

Ответ 4

C++ 11 стандарт

C++ 11 Стандартный черновик N3337 указывает, что std::make_heap используется в конструкторе std::priority_queue в "23.6.4.1 priority_queue constructors":

явный приоритет

2 Эффекты: Инициализирует comp с x и c с y (копируйте конструкцию или перемещайте конструкцию в зависимости от ситуации); вызывает make_heap (c.begin(), c.end(), comp).

И другие методы говорят:

void push (const value_type & x);

Эффекты: c.push_back (x); push_heap (c.begin(), c.end(), comp)

Начиная с более нового n4724, однако, формулировка для не-конструкторских методов становится "как будто", поэтому я думаю, что реальный вызов *_heap методов не гарантирован, только его функциональное поведение.

Шаг отладки в источник g++ 6.4 stdlibc++, чтобы подтвердить, что priority_queue пересылается в make_heap

В Ubuntu 16.04 по умолчанию пакет g++-6 или сборка GCC 6.4 из исходного кода вы можете перейти в библиотеку C++ без дальнейшей настройки.

Используя это, мы можем легко подтвердить, что std::priority_queue является просто оболочкой для семейства std::make_heap с базовым std::vector, что означает, что производительность будет одинаковой.

a.cpp:

#include <cassert>
#include <queue>

int main() {
    std::priority_queue<int> q;
    q.emplace(2);
    q.emplace(1);
    q.emplace(3);
    assert(q.top() == 3);
    q.pop();
    assert(q.top() == 2);
    q.pop();
    assert(q.top() == 1);
    q.pop();
}

Компилировать и отлаживать:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

Теперь, если вы сначала std::priority_queue<int> q в конструктор std::priority_queue<int> q он перейдет в vector конструктор, поэтому мы уже можем догадаться, что std::priority_queue содержит std::vector.

Теперь бежим finish в GDB, чтобы найти конструктор очереди, и снова ступить, что приводит нас к фактическому конструктора очереди /usr/include/C++/6/bits/stl_queue.h:

443       explicit
444       priority_queue(const _Compare& __x = _Compare(),
445              _Sequence&& __s = _Sequence())
446       : c(std::move(__s)), comp(__x)
447       { std::make_heap(c.begin(), c.end(), comp); }

Который явно просто пересылает в std::make_heap поверх объекта c.

Итак, мы открываем исходный файл в vim и находим определение c:

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

      [...]

      _Sequence  c;

и поэтому мы заключаем, что c является vector.

Если мы перейдем к другим методам или изучим источник дальше, мы легко увидим, что все другие методы priority_queue также просто пересылаются в семейство функций std::make_heap.

Выбор кучи против, скажем, сбалансированного BST имеет смысл, поскольку среднее время вставки для кучи меньше, см. Куча против дерева двоичного поиска (BST)

Ответ 5

Если вы не хотите изменять этот вектор, вам следует использовать priority queue поскольку он создает отдельный вектор. Но, если вы можете позволить себе отредактировать его, то, очевидно, использование make_heap было бы лучше, так как оно не создавало вспомогательное пространство и не изменяло этот вектор на месте и, следовательно, экономит место. Кроме того, очередь приоритетов легко реализовать. Например, когда вы используете make_heap при появлении элемента, вы должны использовать две команды: сначала pop_heap а затем pop_back.. но вы можете сделать это только с одной командой в случае очереди приоритетов. Точно так же, нажав элемент в кучу.

Теперь производительность обоих будет такой же, поскольку очередь приоритетов не является контейнером, и она использует некоторый базовый контейнер в качестве вектора или дека, который использует те же операции кучи, что и операции make_heap. Таким образом, вы должны использовать один в зависимости от вашего требования.

Ответ 6

make_heap обеспечивает гибкость за счет инкапсуляции, например, распечатывая кучу.

Интересным использованием make_heap является сортировка слиянием на месте, которая использует make_heap с одной стороны слияния, чтобы достичь наихудшего случая слияния на месте n/2 (log (n/2)).

В этом примере показано использование входного вектора и распечатка созданной кучи:

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(string prefix,vector<int>& v)
{
  cout << prefix;
  for(int i : v)
     cout << i << " ";
  cout << endl;
}

int main()
{
  vector<int> v={1,2,9,0,3,8,4,7,1,2,9,0,3,8,4,7};
  typedef priority_queue< int,vector<int>,greater<int> > MinQ;
  MinQ minQ(v.begin(),v.end()); //minQ
  print("After priority_queue constructor: ",v);

  make_heap(v.begin(),v.end(),greater<int>());
  print("After make_heap: ", v);
  return 0;
}

Выход:

After priority_queue constructor: 1 2 9 0 3 8 4 7 1 2 9 0 3 8 4 7
After make_heap: 0 1 0 1 2 3 4 7 2 3 9 8 9 8 4 7