Was ist der Vorteil von Heaps gegenüber sortierten Arrays?

Ich bin ziemlich neu in Heaps und versuche, mich darum zu kümmern, warum Min- und Max-Heaps als Bäume dargestellt werden, wenn ein sortiertes Array standardmäßig beide Min / Max-Eigenschaften bietet.

Und ein Follow-up: Was ist der Vorteil des Umgangs mit der Komplexität des Einfügens in einen Heap, wenn ein Algorithmus wie das schnelle Sortieren sehr gut sortiert wird?

Kontext: Ich arbeite mit CLRS / MIT 6.006 in Python und habe nur ganzzahlige Darstellungen von Blattwerten gesehen. Ist dies in einer Sprache wie C besser anwendbar, in der jedes Blatt eine Struktur enthält, die nicht einfach sortiert werden kann?

$\small \texttt{find-min}$ (bzw. ), (bzw. ) und sind die drei wichtigsten Operationen eines Min-Heaps (bzw. Max-Heap) und haben normalerweise die Komplexität , bzw. wenn Sie einen Min / Max-Heap durch einen Binärbaum implementieren.$\small \texttt{find-max}$$\small \texttt{delete-min}$$\small \texttt{delete-max}$$\small \texttt{insert}$$\small \mathcal{O}(1)$$\small \mathcal{O}(\log n)$$\small \mathcal{O}(\log n)$

Angenommen, Sie implementieren stattdessen einen Min-Heap durch ein sortiertes (nicht abnehmendes) Array (der Fall für Max-Heap ist ähnlich). und sind von wenn in Ihrer Anwendung nicht erforderlich ist, da dies möglich ist Behalten Sie einen Zeiger , der immer auf das minimale Element in Ihrem Array zeigt. Wenn das minimale Element entfernt wird, müssen Sie nur einen Schritt zum nächsten Element im Array verschieben.$\small \texttt{find-min}$$\small \texttt{delete-min}$$\small \mathcal{O}(1)$$\small \texttt{insert}$$\small p$$\small p$

Der Umgang mit dem Einfügen in ein sortiertes Array ist nicht trivial. Wenn ein neues Element , können wir die binäre Suche verwenden, um seine Position im Array zu finden und es einzufügen. Der Punkt ist jedoch, dass Sie, wenn Sie es dort einfügen möchten, viele alte Elemente (kann ) verschieben müssen, um eine freie Stelle für das neue Element zu schaffen. Dies ist für die meisten Anwendungen ziemlich ineffizient. Sie können das Array auch nach dem Einfügen eines Elements neu sortieren. Dies erfordert jedoch Zeit.$\small e$$\small \mathcal{O}(n)$$\small \mathcal{O}(n\log n)$

Der letzte Punkt, wie Sie eine Datenstruktur implementieren, hängt wirklich von Ihrer Anwendung ab. KEINE einzelne Implementierung ist in allen Fällen am besten. Analysieren Sie Ihre Anwendung, ermitteln Sie die häufigsten Vorgänge und entscheiden Sie dann über die geeignete Implementierung.

Um Ihre Fragen zu beantworten, müssen Sie definieren, welche verschiedenen Aktionen Sie wie oft ausführen werden, und Sie müssen die zeitliche Komplexität jeder Aktion bewerten.

Welche Methode insgesamt besser abschneidet, hängt von der individuellen Komplexität ab und davon, wie oft jede Aktion ausgeführt wird.

Das Sortieren eines Arrays hat eine sehr hohe zeitliche Komplexität. Heap-Operationen sind so billig, dass sie tatsächlich für eine anständige Sortierimplementierung verwendet werden. Die Verwendung eines Heaps zum Auffinden des kleinsten Elements ist definitiv viel schneller als das Sortieren eines Arrays. Zwei Haufen für das kleinste und größte Element sind immer noch viel schneller (aber diese Situation ist ziemlich selten; zum Beispiel möchte bei einem Pferderennen jeder den Sieger wissen, aber es interessiert niemanden, wer zuletzt kommt).

Wenn ein Heap das Sortieren von Arrays absolut übertrifft, werden nur wenige Elemente entfernt oder hinzugefügt, und nach jeder Änderung möchten Sie erneut wissen, welches Element das kleinste ist.