Zeit-Komplexität zu bekommen, min-Elemente von max-heap -

Wurde ich in einem interview gefragt:

Was ist die beste Zeit, Komplexität in immer die min element(s) aus einem max-heap?

Antwortete ich, als O(1) angenommen, die heap-Größe ist bekannt und die heap implementiert ist als ein binary heap ist ein array verwenden. Auf diese Weise gemäß meiner Annahme, der min-Wert ist bei heap_array[heap_size].

Meine Frage ist, dass, wenn diese Antwort richtig ist. Wenn nicht, was ist die richtige Antwort?

InformationsquelleAutor hytriutucx | 2012-07-25

  1. 26

    Meine Frage ist, dass, wenn diese Antwort richtig ist.

    Nein, das ist nicht korrekt. Die einzige Garantie, die Sie haben, ist, dass enthält jeder Knoten die maximale element des teilbaums unterhalb. In anderen Worten, das minimale element kann jedes Blatt in den Baum.

    Wenn nicht, was ist die richtige Antwort?

    Die richtige Antwort ist O(n). In jedem Schritt müssen Sie die traverse Links und rechts sub-trees um die Suche nach dem minimalen element. In der Praxis bedeutet dies, dass Sie brauchen, zu Durchlaufen aller Elemente zu finden, die minimale.

    Könnten wir nicht auch nur ein Blick auf die letzten ceil(n/2) Elemente des Arrays. Es ist immer noch O(n).
    Es klingt wie die Frage richtet sich nicht an eine Umsetzung. Annahmen über die Implementierung würde/sollte das nicht gültig sein, würde ich denken.

    InformationsquelleAutor aioobe

  2. 9

    Besten Komplexität ist O(n). Skizze Beweis:

    • Das minimale element könnte absolut jeder von der untersten Ebene Knoten (in der Tat könnte es auch nicht auf der untersten Ebene, aber wir beginnen mit dieser).
    • Es könnte bis zu n/2 untersten Ebene Knoten.
    • Sie alle müssen untersucht werden, weil die, die Sie suchen, vielleicht in der Letzte Ort, den Sie suchen. Prüfung-all-but-1 von Ihnen nicht sagen, ob Sie die Letzte ist die minimal-oder nicht.
    • Daher Omega(n) Untersuchungen erforderlich.

    Die gebunden ist, fest, da klar können wir es in O(n) durch das ignorieren der Tatsache, dass unser array zufällig ein heap.

    Moral: es ist wohl als heap bezeichnet, weil (wie bei den kleiderhaufen auf Ihrem Schlafzimmer Boden) es ist leicht zu erreichen an der Spitze und schwer zu bekommen auf den rest.

    +1. Aber ich würde einfach sagen, "konnte der Blatt-Knoten".
    das wäre wahrscheinlich besser, da bin ich ziemlich sicher, dass es garantiert mindestens n/2 Blatt-Knoten, wodurch die Omega-gebunden offensichtlicher.
    "in der Tat könnte es auch nicht auf der untersten Ebene" -- Was wäre denn ein Beispiel, wo die min element ist nicht auf die Unterste Ebene?
    Die max-heap-Eigenschaft ist, dass jedes Kind ist kleiner als Ihre Eltern. Nichts über Geschwister. So betrachten Sie einen heap mit "10" an der Wurzel. Sie hat zwei Kinder, die "1" und "9". Die "9" hat zwei Kinder "8" und "7". Dann wird der kleinste Wert nicht auf der untersten Ebene (obwohl, unbedingt, es ist ein Blatt-Knoten).
    Ah, natürlich. Vielen Dank für die Klarstellung! 🙂

    InformationsquelleAutor Steve Jessop

  3. 1

    Min element aus Max-heap :

    1. Suche endlich level = O(n/2)= O(n)

    2. ersetzen gesuchte element mit dem letzten element und verringern Sie die heap-Größe von 1 = O(1)

    3. Gelten Maxheapify auf ersetzte element = O(log n)

    Gesamtzeit = O(n)+O(1)+O(log n) = O(n)

    InformationsquelleAutor parimal

  4. 1

    MINIMUM_ELEMENT -> es dauert O(n) Zeit im Falle eines Max-Heaps und O(1) im Falle des Min-heap.
    MAXIMUM_ELEMENT -> es dauert O(1) Zeit im Falle eines Max-Heaps und O(n) bei Min-heap.

    InformationsquelleAutor Nitishgarg

Schreibe einen Kommentar