Aus Array einen Heap erstellen

[Gast]

Hallo,

kann mir jemand helfen? Ich komm allein mal wieder nicht drauf. Und zwar möchte ich folgendes machen:

* Anders als sonst in Java wird das Array a[] ab dem Index 1 betrachtet
* (der Wert a[0] wird ignoriert); das letzte Element wird unter
* dem als Parameter übergebenen Index "last" gefunden. Der Feldindex
* repräsentiert somit die Knotennummer des Baums.
*
* Die Methode erzeugt schrittweise einen vollständigen,
* linkslastigen Binärbaum (noch keinen Heap!);
* d.h. a[1] wird zur Wurzel, a[2] zum linken Sohn der Wurzel,
* a[3] zum rechten Sohn, a[4] zum linken Sohn des Elements mit a[2] usw.
*
* Der Schlüssel wird im Knoten unter dem Attribut key
* abgelegt, die Knotennummer (also der Index des Felds)
* wird unter dem Attribut no abgelegt.
* Zur Erzeugung eines neuen Knotens dient der
* Konstruktor public Node(int key, int no), z.B.
* Node n = new Node(a, i);
*
* Eine (nicht sehr effiziente, aber einfache) Lösungsidee
* ist folgende: die Knoten werden nacheinander
* (beginnend bei der Wurzel) eingefügt;
* für jeden neuen Knoten wird der (schon eingefügte)
* Vaterknoten anhand seiner Knotennummer gesucht.
* Dann wird der neue Knoten rechts oder links
* unter dem Vater eingefügt.

So weit bin ich gekommen. Nun weiß ich nicht, wie ich weiter komme, dass ich immer das linke und rechte Kind unter die Wurzel hänge?

  public void toTree(int[] a, int last){
 this.root = new Node(a[1], 1);
       
        for (int i=2;i<=last;i++){
            Node n = new Node(a[i], i);
    
        }
    }

Danke für eure Hilfe!!!!!

 

[Gast]

Die Idee lieg wahrscheinlich in der Mathematik.
Dein Array beginn bei eins.

Alle linken Knoten liegen auf dem Array auf : 2 * n
Alle rechten Knoten liegen auf : 2*n +1

so ist zB Array[16]

2*2*2*2....also link tiefe 4

15...ungerade...... 2*7+1 // 2*3+1 // 2*1+1 ...also 3mal rechts

13 ......2*6+1 // 2*3 // 2*1+1 also rechts links rechts

vielleich hilft dir das ein wenig

 

[Guest]

Ja soweit hab ich es schon verstanden. Ich kanns bloß in Java nicht umsetzten.
Vielleciht kann mir ja jemand weiterhelfen?

Danke

 

[Gast]

eine gute seite die es gut erklärt ist

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

man kann auch selber ein wenig arbeiten
so learning by doing...

hoffe es hilft dir und inspiriert dich

 

[Guest]

Die Seite find ich ja ganz gut, aber wirklich weiterhelfen tut sie mir auch nicht, weil hier direkt die heapeigenschaft hergestellt wird. und ich möcht ja eigentlich erstmal nur einen Baum aus dem Array machen. Der Rest kommt glaub irgendwann später.

 

[Gast]

Das Array sebst ist der Baum. Mit den Eigenschaften
wie vorher erklärt.
Wenn man bei 1 beginnt ist es so:

Wer ist der Vater ? --> n/2 (eigentlich (n-1)/2 )
Wer ist der linke Sohn? --> n*2
Wer ist der rechte Sohnt --> n*2 +1

Wie gesagt:

Array[10] --> Vater ist also Array[5]
linker Sohn Array[20]
rechter Sohn Array[21]

Array[11] --> Vater Array[5]
links Array[22]
rechts Array[23]

Dies wäre ein Auschnitt aus dem Baum.

weiter nach oben
Vater von 5 ---> Array[2]
Vater von 2 --> Array[1] bei dir die Wurzel