Какова конкретная цель использования максимальной кучи для приоритетной очереди

Question

Максимальная куча используется для приоритетной очереди из-за дешевого извлечения элемента max.

Однако, пожалуйста, допустите меня.

Разве мы не должны просто искать элемент max в O (N ) раз?

Я знаю, что для извлечения max нам требуется всего O (log N) времени, но прежде чем мы сможем это сделать, нам нужно построить кучу, которая сама по себе требует O (N) времени.

Так почему же мы go из-за такой сложности даже реализуем кучу?

Кроме того, некоторые могут сказать, что для выполнения повторного извлечения max heap является преимуществом.

Но, скажем, мы выполняем k Поисковые операции, поэтому при линейном поиске мы получаем O (KN) == O (N), что совпадает с кучей O (N + K) == O (N)

Если мы выполним N extract max, мы получим O (NLogN), что лучше, чем (NN) == (N ^ 2) поисковых операций.

Но там мы также можем отсортировать массив в O (NlogN) и затем иметь N экстрактов в O (1) время ==> O (NlogN) + O (N).

Поэтому я сомневаюсь, что нам действительно нужны кучи? Когда мы сможем заменить функциональность кучи гораздо более похожей процедурой, если не лучшей.

Что я пропускаю, и для чего реально используются кучи.

Прости мое невежество, и плохое использование грамматики. Не носитель языка, извините: (....

Answer 1

Вы можете использовать кучу для сортировки этого массива за O (n log n) -time в худшем случае (в отличие от быстрой сортировки, если вы не реализуете сложную процедуру выбора сводных значений, которая не очень практична) и без дополнительного пробела (в отличие от Mergesort, если вы не реализуете сложное слияние на месте, которое непрактично вообще ).

Кучи действительно светятся, когда вы смешиваете вставку и извлечение хотя (например, алгоритм Дейкстры, алгоритм Прима).

Answer 2

Подумайте, как приоритетная очередь используется в реальном мире. Вы добавляете что-то, убираете, добавляете, извлекаете и так далее. c. При использовании кучи и Добавить, и Удалить в худшем случае O (log n). Со списком либо Add является O (1), либо Remove является O (1). Другой O (n). Обычно вы хотите, чтобы значение Add было равно O (n), чтобы список всегда сортировался, а операция Peek - O (1).

Итак, учитывая последовательность операций добавления и удаления, когда уже есть 1000 элементов в куче:

Operation     Heap    List
Add           log n     n
Add           log n     n
Remove        log n     1
Add           log n     n
Add           log n     n
Add           log n     n
Remove        log n     1
Remove        log n     1
Remove        log n     1
Remove        log n     1

Это 10 * log (n) для кучи и 5n + 5 для списка. log (n) из 1000 - это около 10. Итак, вы говорите о порядка 100 операций для кучи. Для списка, вы говорите о порядке 5000 операций. Таким образом, куча будет в 50 раз быстрее. Если у вас есть миллион элементов в списке, вы говорите о 200 операциях для кучи и 5 миллионов операций для списка.

Если вы просто хотите go через куча элементов по порядку, тогда нет смысла использовать очередь с приоритетами. Сортированный список работает просто отлично и, вероятно, будет быстрее, чем создание очереди с приоритетами и выборка элементов по одному. (Хотя вы можете в конечном итоге использовать сортировку кучи для сортировки элементов в первую очередь.)

Используйте правильный инструмент для работы.

Answer 3

Рассмотрим сценарий, в котором вы смешиваете N вставки и N извлечения.

Для кучи вы получаете O(NlogN) полных шагов.

Для наивного подхода вы получаете O(N^2) Всего шагов.

Для подхода сортировки (после вставки добавить элементы в конце, после сортировки запроса) вы также получите O(N^2) Всего шагов.