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

19

Я только что заметил что-то, и мне интересно, есть ли причина для этого. За исключением C ++ (std :: priority_queue - это максимальная куча), я не знаю другого языка, который предлагает максимальную кучу.

Модуль Python heapq реализует двоичную минимальную кучу поверх списка.

Библиотека Java содержит класс PriorityQueue, который реализует очередь min-priority.

Библиотека Go содержит модуль контейнера / кучи, который реализует минимальную кучу поверх любой совместимой структуры данных.

Основа Apple Core Foundation содержит структуру CFBinaryHeap, которая реализует минимальную кучу.

Я считаю, что максимальная куча более интуитивна, чем минимальная куча, и я считаю, что технически разница в реализации - это только вопрос смены оператора сравнения. Есть ли реальная причина? Большинству приложений нужна минута, а не максимальная куча? заранее спасибо

design algorithms Бернардо Пирес
источник
Разве они не одно и то же? Я голосую, чтобы закрыть как аргумент.
2
Всего пару дней назад мне понадобилась минимальная куча в C ++, и я был немного раздражен тем, что priority_queue по умолчанию имеет максимальную кучу. Это заставило меня определить operator> в моем пользовательском классе, который уже имел operator <. При работе с графиками вы обычно хотите расставить приоритеты для самых коротких ребер, поэтому вам нужна минимальная куча.
LaC
2
@LaC: вы можете использовать std::not2(std::less<T>()).

Ответы:

9

Как заметили другие, если куча принимает компаратор, то не слишком сложно получить одно или другое поведение. Однако быстрое изучение Google Code позволяет предположить, что минимальная куча гораздо более распространена в реальном коде из-за двух приложений, которые появляются снова и снова.

  • Dijkstra / A * / многие другие алгоритмы кратчайшего пути (потому что частичные пути становятся длиннее).

  • Симуляция событий (потому что время идет вперед).

Кроме того, я бы сказал, что из-за сортировки по умолчанию элементы возвращаются от маленького к большому, так же как и куча по умолчанию.

тугодум
источник
2
Я обычно программирую на C ++, и удивляюсь обратному: почему C ++ не реализует мини-кучу? Как вы сказали, большинство алгоритмов используют минимальную кучу.
Мартин Фиксман
5

Это просто вопрос вкуса. Я не думаю, что будет какая-то конкретная причина. Точно так же, как некоторым людям нравится выражать проблемы оптимизации как минимизацию затрат, в то время как другим нравится максимизировать прибыль.


источник
3

Большинство языков, которые я знаю, позволяют передавать параметр, чтобы решить, должна ли это быть минимальная или максимальная куча. Таким образом, значение по умолчанию является несколько произвольным. Я предполагаю, что для большинства языков это вопрос согласованности, чтобы определить, что является оператором по умолчанию. Для C ++ в stl значение по умолчанию std::lessприводит к минимальной куче.

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

LiKao
источник
3
Я не думаю, что есть такая связь. Вы можете реализовать любой вид кучи, используя <или>. Действительно, std :: less по умолчанию в STL, но они реализуют максимальную кучу вместо минимальной кучи.
LaC
1

По сути, значение индекса является произвольным числом. Если вы считаете, что число представляет приоритет, а большие числа являются более высокими приоритетами, тогда имеет смысл использовать максимальную кучу. Но если числа представляют собой, например, концептуальные пекарские числа («Возьми число»), тогда min-heap имеет больше смысла.

Вы всегда можете конвертировать из одного в другое, взяв 1 дополнение индекса.

Даниэль Р Хикс
источник