priority_queue в C++ — как сделать min-heap вместо max-heap?
Реализую алгоритм Дейкстры, нужна приоритетная очередь, которая отдаёт минимальный элемент. Сделал так:
#include <queue>
priority_queue<int> pq;
pq.push(5); pq.push(1); pq.push(3);
cout << pq.top(); // выводит 5, а мне нужен 1!
Почему очередь с приоритетом в C++ по умолчанию выдаёт максимум? Как переделать её в min-heap, чтобы top() давал наименьший элемент?
2 ответа
Да, std::priority_queue по умолчанию — это max-heap, top() всегда даёт максимум. Это часто сбивает с толку.
Чтобы получить min-heap, есть два способа.
Способ 1 — указать компаратор greater (самый частый):
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5);
pq.push(1);
pq.push(3);
cout << pq.top() << "\n"; // 1 — то, что нужно!
return 0;
}
Запомни этот шаблон наизусть: priority_queue<int, vector<int>, greater<int>> — это min-heap.
Способ 2 — хитрость для ленивых: клади числа со знаком минус, а при извлечении тоже меняй знак. Работает только для чисел, но иногда удобно.
Для Дейкстры обычно хранят пары {расстояние, вершина}:
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, start}); // {dist, node}
Пары сравниваются по первому элементу, так что наверху всегда вершина с минимальным расстоянием — ровно то, что нужно жадному шагу Дейкстры.
Просто чтобы было под рукой, основные операции priority_queue:
pq.push(x); // добавить
pq.top(); // посмотреть верхний (не удаляет!)
pq.pop(); // удалить верхний (ничего не возвращает!)
pq.empty(); // пусто?
pq.size(); // размер
Частая ошибка новичков: думают, что pop() вернёт элемент. Нет — сначала читаешь top(), потом отдельно pop().
