Haufen ?!?

virtuell Realisticer

cHillb3rT schrieb:

Sind das Listen, die während der gesamten Laufzeit eines Programmes verfügbar sind ?

Die Werte verfallen ja, wenn man Sachen in Funktionen oder nur innerhalb eines Buttons programmiert und ich will das mehrere Buttons auf den gleichen Stapel zurückgreifen können !

Deswegen erstellt man solchen Code auch nicht in einem "Button" ;). Schreib dir
Code, der voellig ohne GUI auskommt. Und den nutzt du dann in deiner GUI.

mfg
v R

cHillb3rT

ja aber ist der Haufen ein struct oder ein Objekt einer bestimmten Klasse.... weil zu dem Thema hab ich noch net so viel gefunden bisher !

prolog

Ein haufen (heap) ist eine datenstruktur.
Ein bewerteter binärbaum wenn man so will.
Es gibt bestimmte eigenschaften die ein heap erfüllt.

Bei einem minimum heap ist jedes element in einer schicht kleiner als alle elemente in der darunterliegenden schicht. Das element ist also wurzel eines teilheaps. Das heisst weiter, dass die Wurzel das kleinste element des gesamten heaps ist.

Minumumheap beispiel
Die Zahlen stehen fuer die bewertung des jeweiligen knoten.

Schicht1       2
              / \
Schicht2     3   6
            / \   \
Schicht3   5   4   8

Man kann das kriterium auch umgekehren dass jedes element in einer schicht gerade groesser als elemente der darunter liegenden schicht ist.

Sowas kann man recht leicht selbst implementieren und ich denke so hat sich der aufgabensteller auch gedacht.

sofar ...

cHillb3rT

ahhh okay

und wie sieht so ein Haufen nun im Quellcode aus ? Würde mich auch mal intereessieren....

BasicMan01

Folgendes erklärt das Thema Container und damit Vector ect. ganz gut

http://www.cpp-tutor.de/cpp/le13/le13_04.htm
http://www.cpp-tutor.de/cpp/le18/le18_01.htm

Vielleicht hilft es dir was.

cHillb3rT

Ich hatte gelesen, dass der Heap eine linearisierte Version von einem binären Baum ist. Kann jemand was mit diesem Begriff anfangen ?

Ich hab zwar eine Idee, aber vielleicht denk ich ja falsch und das kann ich dann durch eure Antworten locker ausschließen.

Um einen Heap linear darstellen zu können, muss er ausgeglichen sein.

Der Heap muss überall die selbe Anzahl an Ebenen haben.

      2
    /   \
   4     6
  / \   / \
 5   8 7  10

Elemente dürfen nur in der letzten Ebene von rechts nach links fehlen:
      2
    /   \
   4     6
  / \ 
 5   8 

Sowas hier wäre verboten:
      2
    /   \
   4     6
  /     / \
 5     7  10

Wenn Du jetzt einfach die Ebenen von links nach rechts durchnummerierst, kannst Du sie einfach in einem Vektor ablegen:

2        Ebene 1
    /   \
   4     6     Ebene 2
  / \ 
 5   8         Ebene 3

Linearisiert:
2 4 6 5 8

Im Vektor bekommst Du für ein Element dann seinen Vaterknoten so:
VaterIndex = SohnIndex / 2; ///< Integer-Disivion

AFAIK unterstützt die STL solche Heaps mit diversen Funktionen wie make_heap, push_heap, pop_heap, sort_heap...
Einfach mal auf www.sgi.com/tech/stl auf Index gehen und dann nach Heap suchen.

Jester

Haufen... rofl

Der deutsche Begriff für einen Heap ist übrigens Halde.

endlich hats mal jemand gecheckt

Slin

Jester schrieb:

Haufen... rofl

Der deutsche Begriff für einen Heap ist übrigens Halde.

Klingt beides so negativ, ich persönlich könnte mir nie vorstellen "wichtige Objekte" auf einen Haufen zu werfen oder sie in einer Halde zu lassen...

Braunstein

Laut Leo kann Heap Haufen, Halde oder Menge heißen.