Bottom-up-Konstruktion Haufen

Ich bin ein arbeiten auf eine Frage, wo habe ich 10 Tasten und ich machen eine bottom-up-Konstruktion. Laut meinem Buch soll ich zu konstruieren (n+1)/2 Haufen, die 11/2=5.5 Haufen für den Boden. Dann 11/4 für die 2. Ebene, 11/8 für die 3. und so weiter.

Das problem ist, ich bekomme das als Ergebnis:

(Mit 'a' zum Beispiel)

Bottom-up-Konstruktion Haufen

Seit 11/2=5.5, also Runde ich auf 6, 11/4=2.75, also 3, 11/8=1.375 so 2 -, 11/16=0.6875 so 1.

Selbst wenn ich nicht in der Runde, ich habe noch eine seltsame Haufen. Kann mir jemand erklären, wo ich Durcheinander?

InformationsquelleAutor user977151 | 2011-11-10

  1. 1

    Es schief gegangen, weil nur die Letzte Schicht in einem binären heap ist, darf nicht voll sein. Ein heap mit 10 Elemente sollte wie folgt Aussehen:

            1
     /    \
    2       3
   / \    /\
  4    5  6   7
 /\   /
8  9  10

    Als für die bottom-up-Konstruktion brauchen Sie nicht zu viel darüber nachdenken, die Höhe des heaps. Die grundlegende Idee ist, dass

    1. Knoten ohne Kinder sind trivial Haufen.
    2. Wenn ein Knoten zwei heaps als Kinder können wir konvertieren es zu einem größeren Haufen, die mit einer blubbernden Betrieb.

    So am Anfang wissen wir, dass die Knoten in der 4. Schicht (8, 9 und 10) sind bereits heaps. Wir können dann diese Blase, die die Knoten in der Dritten Ebene zu drehen, Sie in einem Haufen und so weiter.

    Ich verstehe die richtige Antwort ist, aber wie kann ich das Ergebnis mit der Formel, die ich verwendet? Oder vielleicht eine andere Formel zu erreichen?
    Ich vermute, dass die Formel soll nur Arbeit für ganzen Haufen (ie.: n = 2^k - 1)
    Die Frage gab mir eine Sequenz von 10-Schlüssel und bat mich, die machen die Haufen mit bottom-up-Konstruktion. Wie soll ich es machen wenn ich nicht die Formel verwenden?
    Habe ich eigentlich erklärt. Platz die Schlüssel in den Baum, in den posiutions gezeigt, aber in der gleichen Reihenfolge hast du Sie. Der Baum ist nicht ein Haufen, aber Sie wissen, die 4. Ebene ist schon trivial heapified. Sie müssen dann den blubbernden Operationen der Aufruf von heapify in der Dritten Zeile und anschließend die zweite Zeile und so weiter.
    Nur um zu klären, hätte ich 36 12 29... ich würde mal sagen 36 auf der Oberseite dann 12 und 29 auf 2. lvl? Dann mit heap-Eigenschaft würd ich den Schalter 36 mit 12, so dass 12 die Wurzel?

    InformationsquelleAutor hugomg

Schreibe einen Kommentar