Heap als Baum
Ein binärer Heap ist eine sortierte, balancierte binäre Baumstruktur, die in einem Array angelegt wird.
Dabei besteht keine explizite Verknüpfung zwischen einem Parent-Node und seinen beiden Children, sondern auf die Children wird einfach über ihre Position im Array zugegriffen:
Die beiden Children eines Parent-Nodes liegen immer genau hinter dem doppelten Index des Parents.
Daher braucht ein Parent-Node keine extra Children-Property oder sowas, sondern man kann einfach den Parent-Index verdoppeln, und dahinter liegen seine beiden Children.
Oooh - jetzt habichmich so verkünstelt...
... Heap zu erklären, und dann finde ich den englischen Wiki-Artikel
Und dort wird auch noch verlinkt, auf eine gscheite Animation.
Worauf ich noch hinweise ist das Collections.Generic.SortedSet(Of T), mit dem man teilweise auch Anforderungen einer PrioritätenListe abdecken kann.
Das einzige an meinem Rad noch besonders Runde ist die Besonderheit, dassich auf unnötige Tausch-Operationen verzichte (simmerhier bei BubbleSort oderwas?).
Bei mir wird nicht geswapt - sondern einfach "aufgerückt": Denn was soll man den leeren Platz jedesmal ausfüllen, wenner inne nächsten Iteration doch wieder überschrieben wird?
Heap-Bedingung
Ein Heap ist balanciert, wenn für jeden (Parent-)Node gilt: beide Children eines Parents sind größer als ihr Parent. Diese Bedingung stellt sicher, dass der Root-Node bei Index #0 immer der kleinste ist. (Bei MaxHeap ist die Bedingung umgekehrt, und dann ist Root das Maximum).
Durch Entnahme (Heap.Pop()) oder Zufügen (Heap.Push()) gerät die Struktur in Unordnung ("verletzte" Heap-Bedingung), daher schließt sich an diese Operationen immer ein "Re-Balancing" an.
Zwei Beispiele
Also die Zahlenmenge "1 2 3 4 5 6 7 8 9" könnte simpelstenfalls im Heap-Array folgendermaßen angelegt sein:
Aber ein gültiger Heap präsentiert sich normalerweise dem Auge als total unordentlich (heap: Haufen eben)- etwa so:
Auch hier ist die Heap-Bedingung erfüllt, nämlich die beiden Kinder jedes Nodes sind größer - beachte genau die Indicees - rechne jeweils:
Heap.Pop()
Entnommen wird immer der TopNode bei Index #0, und das Re-Balancing erfolgt durch ein lustiges "Aufrücken" der ChildNodes, da der Platz des TopNodes ja neu zu besetzen ist.
Beim Aufrücken wird von den beiden Children immer der jeweils kleinere ausgewählt, und das stellt die Heap-Bedingung (beide Children sind größer) wieder her.
Der allerletzte Node wird außerdem gewissermaßen "heimatlos", denn bei Entnahme verkleinert sich der Heap ja um eins.
Aber sein neuer Platz ergibt sich wie selbstverständlich: Er wird auf diejenige frei werdende Stelle gesetzt, deren kleineres Child immer noch größer ist als der "Heimatlose".
Meist kommt er aber einfach auf den letzte Platz, der beim Aufrücken frei wird.
Poppen wir den o.g. "unordentlichen" Heap einfach mal leer:
Das Aufrücken im Einzelnen:
Also eine Entnahme führt beim Heap mit 9 Nodes zu maximal 3 Zuweisungen. Bei sehr großen Heaps steigt die Anzahl der Zuweisungen aber nur noch geringfügig an, denn nach jedem Aufrücken verdoppelt sich die Schrittweite im Heap, und dadurch isser sehr schnell durchschritten und wieder ausbalanciertt.
ZB. in einem Heap mit 32000 Nodes muß pro Entnahme maximal 16 mal gerückt werden.
Heap.Push(itm)
Das Zufügen verursacht ein Aufrücken in die andere Richtung, und ist noch performanter, denn der Heap muß nur in seltenen Fällen komplett durchschritten werden:
Zunächst wird am Ende des Heaps ein neuer Platz geschaffen.
Dessen Parent errechnet sich durch (childIndex-1)/2, und dieser Parent rückt nach hinten, auf die leere Stelle.
Das wiederholt sich so lange, bis ein Parent gefunden ist, der kleiner als das NewItem ist. Dann rückt nicht der Parent an diese Stelle, sondern NewItem wird dort eingesetzt und fertig.
Während bei Entnahme die Schrittweite mit 1 (oder 2) beginnt und sich jeweils verdoppelt, beginnt man beim Poppen mit der größtmöglichen Schrittweite, nämlich mit der halben Gesamtlänge des Heaps, und halbiert pro Schritt, bis ein geeignetes Plätzchen für NewItem gefunden ist (oder NewItem gelangt auf Index #0 - Root des Baumes).
Bauen wirmal mit der Zahlenfolge 3 2 6 1 9 8 4 7 5 einen Heap auf:
Das Aufrücken im Einzelnen:
Maximal 3 Schritte, aber überwiegend seehr viel weniger
Zum Spaß könnermer auch diesen Heap wieder leer-poppen:
Das Aufrücken im Einzelnen:Man sieht: Unglaublicherweise geht das tatsächlich auf.
Ein binärer Heap ist eine sortierte, balancierte binäre Baumstruktur, die in einem Array angelegt wird.
Dabei besteht keine explizite Verknüpfung zwischen einem Parent-Node und seinen beiden Children, sondern auf die Children wird einfach über ihre Position im Array zugegriffen:
Die beiden Children eines Parent-Nodes liegen immer genau hinter dem doppelten Index des Parents.
Daher braucht ein Parent-Node keine extra Children-Property oder sowas, sondern man kann einfach den Parent-Index verdoppeln, und dahinter liegen seine beiden Children.
Oooh - jetzt habichmich so verkünstelt...
... Heap zu erklären, und dann finde ich den englischen Wiki-Artikel
Und dort wird auch noch verlinkt, auf eine gscheite Animation.
Worauf ich noch hinweise ist das Collections.Generic.SortedSet(Of T), mit dem man teilweise auch Anforderungen einer PrioritätenListe abdecken kann.
Das einzige an meinem Rad noch besonders Runde ist die Besonderheit, dassich auf unnötige Tausch-Operationen verzichte (simmerhier bei BubbleSort oderwas?).
Bei mir wird nicht geswapt - sondern einfach "aufgerückt": Denn was soll man den leeren Platz jedesmal ausfüllen, wenner inne nächsten Iteration doch wieder überschrieben wird?
Heap-Bedingung
Ein Heap ist balanciert, wenn für jeden (Parent-)Node gilt: beide Children eines Parents sind größer als ihr Parent. Diese Bedingung stellt sicher, dass der Root-Node bei Index #0 immer der kleinste ist. (Bei MaxHeap ist die Bedingung umgekehrt, und dann ist Root das Maximum).
Durch Entnahme (Heap.Pop()) oder Zufügen (Heap.Push()) gerät die Struktur in Unordnung ("verletzte" Heap-Bedingung), daher schließt sich an diese Operationen immer ein "Re-Balancing" an.
Zwei Beispiele
Also die Zahlenmenge "1 2 3 4 5 6 7 8 9" könnte simpelstenfalls im Heap-Array folgendermaßen angelegt sein:
Aber ein gültiger Heap präsentiert sich normalerweise dem Auge als total unordentlich (heap: Haufen eben)- etwa so:
Auch hier ist die Heap-Bedingung erfüllt, nämlich die beiden Kinder jedes Nodes sind größer - beachte genau die Indicees - rechne jeweils:
Heap.Pop()
Entnommen wird immer der TopNode bei Index #0, und das Re-Balancing erfolgt durch ein lustiges "Aufrücken" der ChildNodes, da der Platz des TopNodes ja neu zu besetzen ist.
Beim Aufrücken wird von den beiden Children immer der jeweils kleinere ausgewählt, und das stellt die Heap-Bedingung (beide Children sind größer) wieder her.
Der allerletzte Node wird außerdem gewissermaßen "heimatlos", denn bei Entnahme verkleinert sich der Heap ja um eins.
Aber sein neuer Platz ergibt sich wie selbstverständlich: Er wird auf diejenige frei werdende Stelle gesetzt, deren kleineres Child immer noch größer ist als der "Heimatlose".
Meist kommt er aber einfach auf den letzte Platz, der beim Aufrücken frei wird.
Poppen wir den o.g. "unordentlichen" Heap einfach mal leer:
Quellcode
- 1) (2) rückt von Index #2->#0. ChildIndizees von #2 sind #5 und #6.
- Gewählt wird (3 #6), rückt also von #6->#2.
- "Heimatlos" (7 #8) kommt also auf #6.
- 2) (3 #2)->#0 (7 #6)->#2 (8 #7)->#6
- 3) (4 #1)->#0 (5 #4)->#1 (8 #6)->#4
- 4) (5 #1)->#0 (6 #3)->#1 (9 #5)->#3
- 5) (6 #1)->#0 (8 #4)->#1
- 6) (7 #2)->#0 (9 #3)->#2
- 7) (8 #1)->#0 (9 #2)->#1
- 8) (9 #1)->#0
- 9) (leer)
ZB. in einem Heap mit 32000 Nodes muß pro Entnahme maximal 16 mal gerückt werden.
Heap.Push(itm)
Das Zufügen verursacht ein Aufrücken in die andere Richtung, und ist noch performanter, denn der Heap muß nur in seltenen Fällen komplett durchschritten werden:
Zunächst wird am Ende des Heaps ein neuer Platz geschaffen.
Dessen Parent errechnet sich durch (childIndex-1)/2, und dieser Parent rückt nach hinten, auf die leere Stelle.
Das wiederholt sich so lange, bis ein Parent gefunden ist, der kleiner als das NewItem ist. Dann rückt nicht der Parent an diese Stelle, sondern NewItem wird dort eingesetzt und fertig.
Während bei Entnahme die Schrittweite mit 1 (oder 2) beginnt und sich jeweils verdoppelt, beginnt man beim Poppen mit der größtmöglichen Schrittweite, nämlich mit der halben Gesamtlänge des Heaps, und halbiert pro Schritt, bis ein geeignetes Plätzchen für NewItem gefunden ist (oder NewItem gelangt auf Index #0 - Root des Baumes).
Bauen wirmal mit der Zahlenfolge 3 2 6 1 9 8 4 7 5 einen Heap auf:
Zum Spaß könnermer auch diesen Heap wieder leer-poppen:
Dieser Beitrag wurde bereits 22 mal editiert, zuletzt von „ErfinderDesRades“ ()