ternärer Heap in Array-Form

[ersti[09]]

Hallo,

Ich bräuchte mal Hilfe und zwar ist es ja möglich, analog zu einem binären Heap, einen ternären Heap darzustellen. Die Knoten des Heaps werden in Levelorder aufgelistet. Leider weiß ich nicht so ganz, wie das funktionieren soll.

Danke

 

[haf_blade]

Binäre Heaps werden ja üblicherweise dann benutzt, wenn man die einzelnen Objekte einer Datenstruktur nach größer und kleiner sortieren möchte / kann und diese schnell auffinden möchte.

Beispiel von Wikipedia:

Bei dem Wikipedia-Beispiel wäre eine Möglichkeit wie die Zahlen einsortiert wurden die folgende:
1, 2, 3, 6, 5, 4, 7, 12, 10, 8, 11, 9

Bei einem ternären Heap gilt eigentlich genau das gleiche nur, dass halt 3 Pfade zum einsortieren / suchen verwendet werden.

Uploaded with ImageShack.us

Hier die oben benutzt Einfügreihenfolge:
5 4 9 1 2 3 6 7 8 10 11 12

Fügt man die Zahlen in einer anderen Reihenfolge ein enstehen natürlich andere Konstrukte.

Hier noch ein ternärer Heap mit einer unglücklichen Einfügereihenfolge:

Uploaded with ImageShack.us

Die Reihenfolge war 1,2,3,4,5,6 oder 3,2,1,4,5,6 etc.

PS.: Ja ich weiß MSPaint ist crap

 

[ersti[09]]

Cool vielen Dank für die ganze Mühe

hat jemand vllt son kleines Codebeispiel?

 

[fastjack]

Google sollte helfen:

Heapsort ? Wikipedia

n-äre Heaps

 

[ersti[09]]

Ja, google sollte helfen. Leider konnte ich mit dem Code nicht wirklich was anfangen, weil mir die Zeile

const int WIDTH= 8;                // Anzahl der Kinder pro Knoten

spanisch vorkam. Von daher dachte ich, jemand könnte mir ein wirklich einfaches Beispiel geben

 

[fastjack]

Ich denke mal für einen tertiären Baum wäre die Anzahl der Kinder 3. Bei Wiki wird beschrieben, das 8 Kinder optimal wären, Du brauchst aber 3.

 

[ersti[09]]

Ja, das weiß ich ja..