Hardалгоритмы
Чем std::make_heap, push_heap, pop_heap полезны?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Функции для heap-операций над произвольным диапазоном. Лежат в основе std::priority_queue и std::sort (introsort).
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end()); // O(n) — max-heap
// v.front() == 9 (максимум)
v.push_back(7);
std::push_heap(v.begin(), v.end()); // O(log n) — добавляет последний
std::pop_heap(v.begin(), v.end()); // O(log n) — max в конец
v.pop_back(); // удалить бывший max
std::sort_heap(v.begin(), v.end()); // O(n log n) — сортирует- По умолчанию max-heap; для min-heap используйте
std::greaterкак компаратор; - На их основе можно строить свои heap-based структуры.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.