Zeitkomplexität einfügen in einem heap

Ich versuche meistens verstehen die Argumentation hinter dem Großen O und O einfügen eines neuen Elements in einen heap. Ich weiß, ich kann die Antworten online, aber ich wirklich wie mit einem gründlichen Verständnis eher als die Suche nach Antworten online, und nur das Auswendiglernen blind.

So zum Beispiel, wenn wir haben die folgenden heap (dargestellt in array-format)

 [8,6,7,3,5,3,4,1,2]

Wenn wir uns entscheiden, legen Sie ein neues element "4" unsere Palette wird nun wie folgt Aussehen

 [8,6,7,3,5,3,4,1,2,4]

Wäre es platziert in index 9 und da dies ein 0-index-basierten array-seine Eltern-wäre-index 4 die element 5. In diesem Fall würden wir nicht brauchen, etwas zu tun, weil 4 < 5 und es verletzt nicht die binären heap-Eigenschaft. Also am besten Fall ist OMEGA(1).

Allerdings, wenn das neue element fügen wir 100 dann hätten wir zu nennen, die max-heapify-Funktion, die hat Laufzeit O(log n) und damit im schlimmsten Fall das einfügen ein neues element in den heap in O(log n).

Jemand kann mich korrigieren, wenn ich falsch bin, weil ich bin nicht sicher, ob mein Verständnis, oder Argumentation ist 100%?

Ja, du hast Recht. Aber wissen Sie, warum ist das einfügen in heap O(log n) und was bedeutet das?
Würde es helfen, wenn man erklären kann , ich kann nicht das richtige Verständnis...

InformationsquelleAutor user1010101 | 2015-03-02

  1. 7

    Ja, du hast Recht über die best-case-Laufzeit. Und für das worst-case-Laufzeit, Sie sind auch richtig, dass das Theta - (lg n) und der Grund warum ist, dass Sie Ihre heap ist stets AUSGEWOGEN sein, d.h. jede Höhe von einem Satz von Knoten ist voll, außer auf dem unteren Niveau. Also, wenn Sie fügen Sie ein element auf der unteren Ebene, und tauschen Sie von einer Stufe auf die nächste Stufe in Ihrer heap, die Anzahl der Knoten auf dieser Ebene geschnitten wird etwa in der Hälfte und so können Sie nur tun, diese swap-log_2(n) = O(lg n) - mal, bevor Sie auf den root-Knoten (d.h. die Ebene, auf der Spitze des Haufens, der nur einen Knoten). Und wenn Sie legen Sie einen Wert, der gehört an die Spitze des Haufens, der sich zunächst am unteren Rand der heap dann werden Sie in der Tat zu tun haben, im Grunde log_2(n) swaps, um das element an der Spitze des Haufens, wo es hingehört.. Also die Anzahl der swaps im schlimmsten Fall ist Theta(lg n).

    InformationsquelleAutor user2566092

  2. 1

    Ihr Verständnis ist korrekt.
    Da der heap ist ein vollständiger binärer Baum-Struktur, deren Höhe = lg n (wobei n keine Elemente).
    Im schlimmsten Fall (eingefügte element an der Unterseite muss getauscht werden auf jeder Ebene von unten nach oben bis zum root-Knoten zur Aufrechterhaltung der heap-Eigenschaft), 1 swap ist notwendig, auf jeder Ebene. Daher werden die maximale nicht mal das tauschen durchgeführt wird, ist log n.
    Daher, einfügen in einem heap in O(log n) Zeit.

    "fast abgeschlossen"

    InformationsquelleAutor user2700887

Schreibe einen Kommentar