Was ist der Unterschied zwischen A. length und A.heap-size?

Question

Ich habe eine Frage zu Heap-Sortierung. Es steht in einem Algorithmus Buch, dass A.heap-size<= A.length ich den Unterschied zwischen den beiden nicht verstehe. Wenn ein Array einen Heap darstellt, warum besteht die Möglichkeit, dass A.heap-size kleiner als A.length ist. Ich weiß, dass A.heap-size die Anzahl der Elemente innerhalb eines Heap darstellt, also warum ist es nicht vollständig nur gleich der Anzahl der Elemente in einem Array?

Answer 1

Die Invariante der Heap-Sortierung besteht darin, dass die ersten k Elemente des n-Element-Arrays ein Heap auf den k kleinsten Elementen sind und die letzten n-k Elemente die n - k größten Elemente in sortierter Reihenfolge sind. Die letzteren Elemente sind der Grund, warum der Heap nicht das gesamte Array belegt.

Answer 2

Nur um eine Antwort zu erweitern. Lesen Sie weiter dieses Buch.

A.heap_size eines Arrays, ist dieser Ort, wo Heap (max_heap oder min_heap) Strukturelemente platziert werden. Dies ist sinnvoll im Hinblick auf Sortierung oder Warteschlangen. Sie haben Recht: Dies ist die Anzahl der Elemente in einem Heap, aber es ist gleich A.length nur bei erste Iteration von Heap-Sortierung.

Am nächsten Iteration nach Wurzel des max_heap Baumes (A[1]) mit A[i] = A[A.length] (letztem Elemente in Array A) auszutauschen, das A[1] Element wird das letzte Element der A sein und A.heap_sort Wert wird um 1 und max_heap verringert wird Struktur sollte max_heapified sein: A[Parent(i)] >= A[i], wobei Parent(i) i/2 des Heap-Baums zurückgibt.

Answer 3

Von Cormen-Algorithmus Lehrbuch, das ich verwende: (dies half mir)

Answer 4

a.length die Gesamtangesichts der, die in nicht von Elementen nicht von Elementen des Arrays während A.heap Größe gibt sortierte Reihenfolge oder keine der Elemente, die der Heap-Eigenschaft folgen ........ Und A.length-A.Heap-Size oder sogar nicht sortiert auch jetzt und muss in Zukunft sortieren.