heap erzeugen

[ghost dog]

hätte auch noch ne frage wie ich einen heap erzeuge.
gibt es da grundsätzlich mehrere möglichkeiten einen heap zu erzeugen?
muss einzig die bedinnung erfüllt sein, dass der knoten grösser als die kinder sind bzw. ist es egal ob das linke kind grösser als das rechte ist und umgekehrt?
funktioniert das versickern quai von unten nach oben??
fragen über fragen...
naija. vielleicht hat jemand einige tipps für mich.
vielen dank!
--> ghost dog

[MarvinTheRobot]

also so wie ich das verstanden hab geht das so

man schreibt die zahlenfolge so wie sie steht in den baum hinein, element für element wie es dasteht (z.b. 1 5 6 4 3 2 9 7 8),

1 ist an der wurzel und dann von links nach rechts auffüllen.

dann von unten weg die falschen knoten suchen (wenn zum beispiel 6 als knoten für 9 und 2 da steht) und austauschen wobei 9 mit 6 getauscht wird.... also immer mit dem größeren von den beiden elementen.... bis das größte element oben steht und der rest auch passt, dann sollts eigentlich stimmen.

wenn ich falsch liegt korrigiert mich bitte. ;-)


mfg, Phil.

[bluefoxx]

is richtitsch! wie pavel pipovitsch oder bronco kulitschka sagen würden! :)

[MarvinTheRobot]

anscheinend doch net.... in einem anderen thread stehts anders und im rep haben wirs auch anders gemacht.

[moose]

ich stell mir das erstellen vom heap so vor:
http://frost.feig.at/informatik-forum/showthread.php?s=&threadid=980&pagenumber=2

[sabs]

bin ein bisserl verwirrt:
am beginn trage ich die zahlen in meinen heap ein, der auch eine liste sein kann,
dann suche ich von oben od. von unten die knoten, an denen die heap-eigenschaft verletzt ist?
bsp:
5,2,4,6,4,3,2,6 sind meine zahlen
dann füge ich sie so in die liste ein:
5 2 4 6 4 3 2 6 beim linkesten 2-er ist meine h-bed. verletzt->
5 6 4 2 4 3 2 6 so und jetzt? die h-bed. ist beim link. 5-er und beim link. 2-er verletzt.

steh irgendwie auf der leitung. hab das eigentlich scho amal checkt :-(

[bla]

ich hab mir schon anfang des semesters mal die arbeit gemacht alle sortier pseudocodes abzutippen (das warn spass :D )
nach jeder versickere operation:
beginn bei i = 3 da Math.floor(7 / 2)) 7 weil i0 = 0

i = 3: 5,2,4,6,4,3,2,6
i = 2: 5,2,4,6,4,3,2,6
i = 1: 5,6,4,6,4,3,2,2
i = 0: 6,6,4,5,4,3,2,2

warum kann es auch in einer liste sein?
sicher möglich ist es aber dort das 2*i (+1) te element zu bekommen dürfte etwas länger dauern.
oder meinst du einfach du scheibst es auf dem papier als liste?
wenn ja vergiss den letzen absatz ;)

[golja]

2sabs: du mußt ja bei der abgerundeten hälfte des feldes anfangen und dann nach links bis zum ersten element gehen. außerdem sind wir ja in einer schleife, der 2er tauscht sich ja noch weiter. erst am ende ist die heapbedingung erfüllt.

[sabs]

so, hab mir die 2 antworten auf meine frage durchgelesen! irgendwie kommt es mir immer so vor, als ob ich net ganz deutsch schreiben würde. wollt eigentlich nur wissen ob 5er oder 2er: das war hier die frage (und das warum!)
hab voll verzweiflung weiter gelesen und dann wirklich:

danke golja!
ein wort hat genügt, um mich von der leitung zu schubsen! SCHLEIFE hat dann doch noch den schalter umgelegt!

lg