Warum bieten die meisten Sprachen eine Min-Heap-Implementierung anstelle einer Max-Heap-Implementierung an?

19

Mir ist gerade etwas aufgefallen und ich frage mich, ob es dafür einen Grund gibt. Mit Ausnahme von C ++ (std :: priority_queue ist ein maximaler Heap) kenne ich keine andere Sprache, die einen maximalen Heap bietet.

Pythons Heapq-Modul implementiert einen binären Min-Heap über einer Liste.

Javas Bibliothek enthält eine PriorityQueue-Klasse, die eine min-priority-queue implementiert.

Die Bibliothek von Go enthält ein Container- / Heap-Modul, das einen Min-Heap über jeder kompatiblen Datenstruktur implementiert.

Das Core Foundation-Framework von Apple enthält eine CFBinaryHeap-Struktur, die einen Min-Heap implementiert.

Ich finde einen Max-Heap intuitiver als einen Min-Heap und technisch gesehen ist der Implementierungsunterschied nur eine Frage der Änderung eines Vergleichsoperators. Gibt es einen wirklichen Grund? Die meisten Anwendungen benötigen einen minimalen statt einen maximalen Heap? Danke im Voraus

design algorithms Bernardo Pires
quelle
Sind sie nicht genau dasselbe? Ich stimme abschließend als argumentativ.
2
Vor ein paar Tagen brauchte ich einen Min-Heap in C ++ und war ein bisschen verärgert, dass priority_queue standardmäßig einen Max-Heap verwendet. Es zwang mich, operator> für meine benutzerdefinierte Klasse zu definieren, die bereits operator <hatte. Wenn Sie mit Diagrammen arbeiten, möchten Sie in der Regel die kürzesten Kanten priorisieren, sodass Sie einen minimalen Heap benötigen.
LaC
2
@ LaC: Sie können verwenden std::not2(std::less<T>()).

Antworten:

9

Wie andere beobachtet haben, ist es nicht allzu schwer, das eine oder andere Verhalten zu finden, wenn der Haufen einen Komparator akzeptiert. Eine schnelle Durchsicht von Google Code legt jedoch nahe, dass Min-Heap im tatsächlichen Code weitaus häufiger vorkommt, da zwei Anwendungen immer wieder auftauchen.

  • Dijkstra / A * / viele andere Algorithmen für kürzeste Wege (weil Teilwege länger werden).

  • Ereignissimulation (weil die Zeit vergeht).

Ich würde auch argumentieren, dass die Standardsortierung kleine bis große Elemente zurückgibt, ebenso wie der Standardheap.

Langweiler
quelle
2
Normalerweise programmiere ich in C ++ und frage mich das Gegenteil: Warum implementiert C ++ keinen Min-Heap? Wie Sie sagten, verwenden die meisten Algorithmen einen Min-Heap.
Martín Fixman
5

Es ist nur Geschmackssache. Ich glaube nicht, dass es einen bestimmten Grund geben wird. Es ist so, als würden manche Leute Optimierungsprobleme gerne als Minimierung der Kosten ausdrücken, während andere gerne die Maximierung des Gewinns ausdrücken.


quelle
3

Die meisten Sprachen, die ich kenne, erlauben die Übergabe eines Parameters, um zu entscheiden, ob es sich um einen Min- oder Max-Heap handelt. Der Standardwert ist also etwas willkürlich. Ich denke, für die meisten Sprachen ist es eine Frage der Konsistenz, den Standardoperator zu definieren. Für C ++ in der STL ist die Standardeinstellungstd::less zu einem Min-Heap.

Die Konsistenz der Verwendung std::lessvon Standard überall bedeutet, dass Sie diesen Vergleich nur implementieren müssen, wenn Sie irgendeine Art von Datenstruktur verwenden, und Sie müssen sich nicht entscheiden, welche Datenstruktur Sie später beim Entwerfen Ihrer Klassen verwenden werden. Ich denke, es ist dasselbe für andere Sprachen, mit dem einzigen Unterschied, dass ein Vergleich größer als der Standard ist.

LiKao
quelle
3
Ich glaube nicht, dass es eine solche Verbindung gibt. Sie können jede Art von Heap mit <oder> implementieren. In der Tat ist std :: less die Standardeinstellung in STL, aber sie implementieren einen max-Heap anstelle eines min-Heap.
LaC
1

Grundsätzlich ist der Indexwert eine beliebige Zahl. Wenn Sie der Meinung sind, dass die Nummer eine Priorität darstellt und größere Nummern höhere Prioritäten haben, ist ein maximaler Heap sinnvoll. Aber wenn die Zahlen zum Beispiel konzeptionelle Bäckereizahlen darstellen ("Take a number"), ist Min-Heap sinnvoller.

Sie können jederzeit von einem zum anderen konvertieren, indem Sie das 1-Komplement des Index verwenden.

Daniel R Hicks
quelle