Da ein Heap eine Kombination aus binärem Baum und Array ist, behält der gesamte Heap beim Sortieren die Form eines vollständigen Baums?Heapsort-Frage
Für eine Hausaufgabe muss ich den Heap und Array für jeden Schritt der Sortierung verfolgen, und ich bin mir nicht sicher von der Baumdarstellung.
Ein Heap ist immer ein perfekt ausgewogener, vollständig bevölkerter Baum, der der Heap Invariant folgt. Bei einem Min-Heap ist der Wert eines Knotens immer größer oder gleich dem Wert jedes seiner untergeordneten Elemente.
Heapsort erstellt einen Heap aus unsortierten Daten (O (n) time), entfernt dann wiederholt das oberste Element des Heap (O (lg n) -Zeit, da der Heap bei jedem Entfernen beibehalten werden muss) und legt es ab in ein Array. Bemerkenswerterweise funktioniert dies nur, wenn der Heap unveränderlich bleibt - was unter anderem eine perfekte Balance und einen gültigen Baum erfordert.
Der binäre Baum ist nicht die effizienteste Darstellung eines Heaps; the Wikipedia article on binary heaps erklärt sehr gut, wie man ein Array benutzt, um eins darzustellen. The article on Heapsort erwähnt ein nützliches Detail: Sie können an Ort und Stelle sortieren, indem Sie das Leerzeichen am Ende des Heap verwenden, wenn Sie die Array-Darstellung verwenden, um Ihr Ausgabe-Array zu erstellen, da der Heap immer balanciert und das Entfernen eines Elements schließlich das physisch freigibt letzte Zelle des Arrays, das den Heap darstellt.
Die Implementierung, die der Professor angegeben hat, ist in-place. Ich war mir nur nicht sicher, ob es notwendig war, den Heap nach jedem Sortierlauf neu zu erstellen. – Jason
Sie müssen den Heap nicht vollständig neu erstellen, aber Sie müssen den Fehler neu ausgleichen. Es ist nur die Standard-remove-top-Element-Funktion. –
Erste Treffer auf Google: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm –