Очередь с приоритетом в стандартной библиотеке C++ (std::priority_queue) по умолчанию основана на структуре данных куча (heap). Конкретно — на максимальной куче (max-heap) по умолчанию, где наибольший элемент всегда находится в корне.
Это позволяет эффективно выполнять две ключевые операции очереди с приоритетом:
top() + pop()): O(log N)push()): O(log N)Под капотом std::priority_queue использует произвольный контейнер с поддержкой случайного доступа (по умолчанию std::vector) для хранения элементов и поддерживает свойство кучи, вызывая глобальные функции std::make_heap, std::push_heap и std::pop_heap.
c