max-heap und einfügen

Habe ich die ein integer-array der Größe 10. Ich brauche zum zeichnen des vollständigen binären Baumes, die ich habe. Jetzt muss ich einfügen das die anderen drei Elemente mit siftup-Verfahren. Zeigen die max-heap nach jedem einfügen.

Ich m nicht sicher was ist, das zeigen die max-heap nach jedem einfügen.
wird das bedeuten, ich muss die Größe von max-heap jedes mal, wenn ich stecken Sie ein element?

Definition (max-heap) ein HEAP(X)
Sei X eine Total geordnete Menge. Ein Haufen auf X ist entweder leer, ∅, oder es ist ein vollständiger binärer Baum t, der aus nt ≥ 1 Knoten zu jedem Knoten, die einen Wert von X zugewiesen wird, so dass:
Wert von Knoten i ≤ Wert der übergeordnete Knoten i, i = 2,3,...,nt.
Die Größe des heap ist die Anzahl der Knoten im Baum. Ein heap ist leer, wenn und nur wenn seine Größe ist 0.

die definition max-heap ist, wie diese, aber es sieht aus wie ein wenig zweideutig für mich.

the definition of max heap is like this, but it looks like a bit ambiguous to me. Das Teil sieht mehrdeutig? Das ist genau der Teil, auf dem Sie den Fokus auf Ihre Frage.

InformationsquelleAutor johnnily | 2012-11-25

3

Einfach ausgedrückt, ist ein max-heap ist ein heap, in denen der Wert des übergeordneten Elements ist größer als der Wert eines seiner Kinder. Wenn Sie zog Ihren ersten vollständigen binären Baum, ist es in form von einem max-heap bereits?
Sift-up (in meiner Schule nannten wir es bubble-up, aber neben dem Punkt) ist ein wenig kompliziert zu erklären, auf einen thread wie diesen, so Stimme ich mit @DanteisnotaGeek. Der wikipedia-Artikel hat eine gute Grafik wie ein sift-up-Verfahren arbeitet.
Um zu zeigen, ein max-heap nach der insertion und fordert Sie auf, zeichnen Sie den binären Baum, so dass es erfüllt die max-heap-Eigenschaft nach jeder Einfügung. Also am Ende sollten Sie Ihren ersten Baum, einen Baum mit Ihrem ersten insertion, eine zweite einfügen, und eine Dritte Aufnahme, also insgesamt 4 Bäume.

ich danke Ihnen so sehr..

InformationsquelleAutor Nagia
8

Müssen Sie zeigen den resultierenden Baum nach jeder insetion. Ich meine, wenn Sie zunächst Sie haben einen Haufen
```
   3
  /\
 1   2
```
Und fügen Sie eine 5 ein, wird es beginnen, an das Letzte heap-position und Blase bis die heap-Kopf:
```
    3           5
   /\         /\
  1   2  =>   3   2
 /          /
5           1 
```
Entsprechend, Wenn Sie legen Sie eine 4, dann:
```
    5           5
   /\         /\
  3   2  =>   4   2
 /\         /\
1   4       1   3
```
diese Antwort verdient viel mehr votes, vielen Dank für die tolle demonstration.

InformationsquelleAutor Juan Lopes
0

In Haufen, in jedem moment vom root-Knoten an den Blatt-Knoten ist bestellt und linear:

Beim einfügen von einem element zum nächsten slot im heap, die Linie, die Bestellung geändert werden:

so, der Letzte Schritt der Aufnahme werden neu anordnen eine lineare Datenstruktur: bubble-sort

InformationsquelleAutor 宏杰李

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.