Куча (heap) в C++ через make_heap/push_heap/pop_heap — как это работает?
Знаю, что есть priority_queue, но в одном разборе видел, что кучу делают прямо на векторе через make_heap, push_heap, pop_heap из <algorithm>. Зачем это нужно, если есть готовая очередь с приоритетом?
И как этими функциями вообще пользоваться? Пробую make_heap(v) — не компилируется. Что я делаю не так?
2 ответа
Не компилируется, потому что эти функции принимают итераторы, а не сам контейнер: надо make_heap(v.begin(), v.end()).
Эти функции из <algorithm> превращают обычный vector в кучу прямо на месте. По умолчанию — max-heap (наверху максимум, лежит в v.front()).
Полный пример:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {3, 1, 4, 1, 5};
make_heap(v.begin(), v.end()); // строим кучу за O(n)
cout << v.front() << "\n"; // 5 — максимум
v.push_back(9); // сначала добавляем в конец
push_heap(v.begin(), v.end()); // потом «просеиваем» новый элемент
cout << v.front() << "\n"; // 9
pop_heap(v.begin(), v.end()); // переносит максимум в КОНЕЦ вектора
v.pop_back(); // и только потом физически удаляем
cout << v.front() << "\n"; // снова 5
return 0;
}
Главная неочевидность: pop_heap не удаляет элемент, а перемещает корень (максимум) в самый конец и восстанавливает кучу на оставшейся части. Удаляешь его уже сам через v.pop_back().
Зачем это, если есть priority_queue? В 90% случаев бери priority_queue — она удобнее и инкапсулирует всё это. Низкоуровневые heap-функции нужны, когда тебе требуется доступ ко всем элементам кучи как к обычному вектору, или ты строишь что-то нестандартное (например, heapsort вручную).
Для min-heap добавь компаратор greater<> во все три вызова — он должен быть одинаковым везде, иначе куча сломается:
make_heap(v.begin(), v.end(), greater<int>());
push_heap(v.begin(), v.end(), greater<int>());
pop_heap(v.begin(), v.end(), greater<int>());
Ещё есть sort_heap — отсортирует уже построенную кучу (это и есть heapsort). И is_heap — проверит, является ли диапазон кучей.
