Почему min-heap предпочтительнее max-heap для реализации очереди с приоритетами?

Question

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

И почему стоит использовать кучу для реализации очереди с приоритетами?

Answer 1

Вы используете то, что необходимо.Иногда 1 является «наивысшим приоритетом», за которым следуют 2, 3, 4 и т. Д. В этом случае вы бы использовали минимальную кучу для своей очереди приоритетов.В других случаях «наивысший приоритет» определяется так, что вещь с более высоким номером обрабатывается первой.В этом случае вы должны использовать максимальную кучу.

Минимальная куча гарантирует, что вещь с самым низким значением находится в корне кучи и будет удалена первой, когда вы извлечете ее из кучи.Максимальная куча гарантирует, что самая важная вещь находится в корне кучи.

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

Answer 2

Мин-куча требуется для большего количества алгоритмов, таких как Дейкстра.Но в действительности min-heap и max-heap эквивалентны, если вы просто отрицаете все элементы.

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