Angst vor Binärbäumen, Heapsort programmieren

Computer: Software & Programmierung Java
#1

Hilfe ich habe Angst vor Binärbäumen, man könnte schon sagen eine Phobie. ich will aber Heapsort programmieren. Was soll ich tun???

#2

Was ist dass für eine blöde Frage?!? :smiley:
Es ist gar nicht so schlimm wie man am Anfang denkt.
Also man kann Heapsort auch programmieren, ohne irgend eine komplizierte Baumstruktur programmieren zu müssen!
Angenommen du willst aufsteigend Sortieren:
Wenn man vorher schon weiß wie viele Elemente man sortieren will,
kann man mit eben einem Array dieser Größe arbeiten,
so dass gilt jeder Vaterindex v hat bis zu 2 Kinder l,r (linkes und rechtes) die vom Wert her im Array a größer sind
Also: a[v]
Einfügen(a,n) // oft auch „Aufsteigen“ oder „HeapifyUp“
// 0 AND a[v]>=a[k]) {
vertausche(a,v,k)
k=v;
v=(k-1)/2
}

Wenn das ganze Array a ein Heap ist (also n==a.length),
dann steht das Minimum immer ganz oben auf Index 0.
Nun fängst du einfach an alle Minima rauszunehmen und der Reihe nach hintereinander zu schreiben.
Diese sind dann sortiert.
Zum rausnehmen des Minimums macht man folgendes:
Zuerst nimmt man die Wurzel an Index 0 (Minimum) weg
und vertauscht sie mit dem letzten Heapelement (an Index n).
Und macht den Heap eins kleiner(n=n-1).
Da das Element an Index 0 jetzt aber nicht mehr das Minimum ist,
lässt man es quasi im Heap „absinken“ bis es an der richtigen Stelle ist.
Man vertauscht dazu immer das Minimum aus dem aktuellen Element k und seinen beiden Kindern l und r nach oben, bis nicht mehr getauscht werden muss, weil das Minimum schon oben steht/der Vater ist.

Algorithmus „Pseudocode“

EntferneMinimum(a,n) // oft auch "Absinken" oder "HeapifyDown" 
// Entfernt die Wurzel(Minimum) und ordnet dann den Heap wieder richtig
 n = n-1 // verkleinere den Heap 
 // vertausche Wurzel mit dem dadurch entfernten Element hinter dem Heap
 vertausche(a,0,n) 
 // stelle Heapeigenschaft wieder her:
 k = 0
 fertig = false
 do {
 l = 2\*k+1
 r = l+1
 if (l 

Der vollständige Algorithmus ist dann einfach:



    
    SortiereAbsteigend(a, n) // Heapsort 
     // Heap erstellen 
     for (i = 1 to n-1) do {
     Einfügen(a,i)
     }
     // Minimum für Minimum rausnehmen, bis Heap leer
     for (i=n to 1) do {
     min = EntferneMinimum(a,i)
     a[i-1] = min
     }




Jetzt hab ich viel mehr geschrieben als ich eigentlich wollte
und ich hoffe das es wenigstens was nützt.


hier eine Array-implementation von Heapsort.
[http://www.java-tips.org/java-se-tips/java.lang/heap...](http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html)
und noch eine:
[http://www.tutorials.de/forum/algorithmen-datenstruk...](http://www.tutorials.de/forum/algorithmen-datenstrukturen-mit-java/343745-heap-sort-erstellen.html)

Gruß
VoidZer0
#3

Schöne Antwort, VoidZer0, aber der Ursprungsposter hatte ja wahrscheinlich doch keine Angst vor Binärbäumen, sondern wollte nur seine Hausaufgabe von irgendwem hier gemacht bekommen :wink:

Gruss
norsemanna

#4

Schöne Antwort, VoidZer0, aber der Ursprungsposter hatte ja
wahrscheinlich doch keine Angst vor Binärbäumen, sondern
wollte nur seine Hausaufgabe von irgendwem hier gemacht
bekommen :wink:

Mist! Jetzt wo du es sagst, kann ich das wohl kaum ausschließen.
Wäre allerdings schade, wo ich mir doch ernsthaft Mühe gegeben habe es halbwegs verständlich
ohne zu viel Fachchinesisch zu erklären.

Aber ich Trottel mag ja auch Bäume und Wälder, sowie Blüten, Stängel und Datenfelder.
Doch die Menschen, sie sind wie Graphen:
sie haben viele Ecken und Kanten.
Meine Naivität soll mich mal wieder bestrafen
ich hoffte doch nur er hätt’s gut verstanden.
Missbraucht er nochmals meine Kompetenz,
verjage ich ihn aus meiner Arboreszenz!
Ohh, es ist so traurig, einsam und bitter-kalt
so ganz allein im Tiefensuchewald!
((°.^)/)
Gibt’s eigentlich schon sowas wie algorithmische Poesie? :smiley:

1 Like