D a t e n s t r u k t u r    H e a p

HMO,   Warendorf,   Januar 1998



Aufgabe o)
Kann man die Prozedur "mache_heap" auch durch ein Variante von Quicksort ersetzen ?


Die Antwort ist "ja" ! Ein sortiertes Array ist immer je nach Sortierung Minimum- oder Maximum-Heap. Die Begründung ist recht einfach: jedes Element des Arrays mit kleinerem Index ist kleiner als die mit größerem, wenn das Array aufsteigend sortiert ist. Wenn das Array als schichtweise aufgebauter Binärbaum aufgefaßt wird, dann sind demnach die Elemente in einer tieferen Schicht immer größer als die in den höheren Schichten. Das ist dann erst recht ein Heap.

Man bedenke aber, daß der Heap schneller mit "make_heap" aufgebaut werden kann. Die vollständige Sortierung mit Quicksort ist jedenfalls aufwendiger.



HTML-Texte: ADT Heap HAUPTTEXT

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998