Wird Heapsort jemals in der Praxis verwendet? [geschlossen]

8

Quicksort übertrifft Heapsort in der Praxis. Mergesort ist der einzige stabile der 3 (in Plain-Vanilla-Implementierungen). Es ist also entweder Quicksort oder Mergesort, die je nach der Situation verwendet werden (In-Place im Speicher oder externe Sortierung etc.).

Gibt es also jemals einen Fall, in dem die Heap-Datenstruktur tatsächlich zum Sortieren verwendet wird? Egal wie sehr ich "Google" oder versuche, Anwendungen zu erstellen, fast immer wählt man merge / quick-sort over heapsort. Ich habe noch nie einen Fall gefunden, in dem Heap-Sort tatsächlich in meinem Berufsleben verwendet wird. Was wäre eigentlich ein guter Anwendungsfall für den Heapsort in der Praxis (wenn überhaupt), aus Neugierde?

    
PhD 30.12.2012, 01:12
quelle

1 Antwort

5

Einige Vorteile aus meinem Kopf (wird diese Liste nach einigen Nachforschungen ändern:

  • Fast-sortierte Sätze profitieren von der Sortierung nach Heapsort.
  • Weltraumbewusste Umgebungen bevorzugen oft die O (1) -Komplexität von Heapsort. Denken Sie an eingebettete Systeme.
  • Riesige Datensätze profitieren von der garantierten Laufzeit von O (nlog n) im Gegensatz zur wahrscheinlichen besseren Laufzeit von quicksort. Denken Sie an Medizin, Raum, Lebenserhaltung usw.
David Titarenco 30.12.2012, 01:25
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Ist es möglich, ein Hover-Element in jQuery auf zwei divs mit show and hide-Funktionalität anzuwenden?