Какова временная сложность поиска минимального элемента в минимальной куче?
Я читал проблему 1 (часть-б), упомянутую в этот документ:
Нахождение минимального элемента двоичной минимальной кучи занимает логарифмическое время:
T/F?
Это должно быть правдой, потому что когда мы создаем максимальную кучу, сложность времени O(logn)как уже упоминалось Вот.
Точно так же, если я создаю минимальную кучу, это должно быть O(logn), Минимальная куча аналогична максимальной куче, просто в C ++ по умолчанию создается максимальная куча, и нам нужно написать собственный компаратор для минимальной кучи. Тогда какая разница?
Решение
Сложность времени, чтобы найти минимальный элемент в минимальной куче O(1)Это основная цель такого контейнера. Это было буквально сделано, чтобы найти самый маленький (или самый большой) элемент в постоянном времени. Операция, которая O(logn) является вставка. Как уже упоминали другие, pop это также O(logn) потому что он удалит наименьший (или наибольший) элемент, а затем принудительно переупорядочит, чтобы гарантировать, что новый наименьший (или наибольший) элемент теперь находится в верхней части кучи.
От cppreference
Очередь приоритетов — это контейнерный адаптер, который обеспечивает поиск в постоянном времени самого большого (по умолчанию) элемента за счет логарифмическая вставка и извлечение.
Для всех намерений и целей минимальная куча и максимальная куча — это одно и то же, за исключением компаратора. На самом деле, на практике минимальная куча, как правило, std::priority_queue, и если вы хотите Maxheap вы используете std::less и если вы хотите minheap, вы используете std::greater для Compare аргумент шаблона
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
Другие решения