Когда я должен использовать make_heap против очереди приоритетов?

У меня есть вектор, который я хочу использовать для создания кучи. Я не уверен, должен ли я использовать функцию make_heap C++ или поместить мой вектор в очередь с приоритетами? Что лучше с точки зрения производительности? Когда я должен использовать один против другого?

Источник

6 ответов

Решение

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

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

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

Источник

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

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

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

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 Сначала это входит в 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)

Источник

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

Источник

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 сохранять приоритетность свойства кучи (имеет значение только первый элемент, который будет наибольшим).

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

Источник

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

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

Источник

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
Источник
Другие вопросы по тегам