Mediumконтейнеры
Чем priority_queue полезен и как реализован?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::priority_queue — адаптер, представляющий max-heap по умолчанию: top() даёт наибольший, push()/pop() за O(log n). Реализован поверх vector/deque через std::make_heap/push_heap/pop_heap.
std::priority_queue<int> pq; // max-heap
pq.push(3); pq.push(1); pq.push(5);
pq.top(); // 5
pq.pop();
// min-heap — через компаратор
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;- Применение: алгоритм Дейкстры, top-K, scheduling, любые сценарии с приоритетами;
- O(log n) для push/pop, O(1) для top;
- Не поддерживает итерацию — доступ только к top.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.