Daily bit(e) C++. std::make_heap, std::push_heap, std::pop_heap, std::sort_heap
Добавлено 30 июля 2026 в 01:32
Daily bit(e) C++ 52, альтернатива std::priority_queue и std::set: алгоритмы кучи: std::make_heap, std::push_heap, std::pop_heap и std::sort_heap.
Набор алгоритмов кучи (std::make_heap, std::push_heap, std::pop_heap и std::sort_heap) может использоваться в качестве замены std::priority_queue и std::set, когда желательно хранить элементы в непрерывном хранилище, или когда требуется дешевое извлечение элементов.
За преимущества мы платим более подверженным ошибкам интерфейсом.
#include <vector>
#include <algorithm>
#include <string>
std::vector<int> data{8,2,1,7,4,5,3,6,9};
// инициализировать max-heap
auto begin = data.begin(), end = data.end();
std::make_heap(begin, end);
// извлекаем каждый элемент из кучи,
// получая отсортированный порядок в векторе
while (begin != end)
{
// pop_heap меняет местами максимальный элемент
// с последним элементом в диапазоне, поддерживая порядок в куче
std::pop_heap(begin, end--);
// проходимся через 9,8,...
}
// data == {1, 2, 3, 4, 5, 6, 7, 8, 9}
std::vector<std::string> labels{"world","bye","fox","lazy","dog"};
std::make_heap(labels.begin(), labels.end());
// labels теперь в порядке кучи
// извлекаем элемент из кучи, не удаляя его из вектора
std::pop_heap(labels.begin(), labels.end());
// модификация на месте
labels.back()[0] = 'e';
// вставка обратно в кучу
std::push_heap(labels.begin(), labels.end());
std::sort_heap(labels.begin(), labels.end());
// labels == {"bye", "dog", "eorld", "fox", "lazy"}