So löschen Sie in einer heap-Datenstruktur?

Verstehe ich, wie das löschen der root-Knoten aus einem max-heap-aber ist das Verfahren zum löschen eines Knotens aus der Mitte zu entfernen und ersetzen die Wurzel wiederholt, bis der gewünschte Knoten gelöscht wird?

  1. Ist O(log n) - die optimale Komplexität für dieses Verfahren?
  2. Auswirkungen hat dies auf the big O Komplexität, da die anderen Knoten müssen gelöscht werden, um zu löschen, die einen bestimmten Knoten?
warum würden Sie wollen, um einen node zu löschen, die in der Mitte in einen max-heap?
Eine sehr Reale Nutzung eines solchen was ist ein heap-Repräsentation der priority queue der eingeplanten jobs, und jemand bricht ein die jobs.
Ich habe vor kurzem realisiert die LPA* pathfinding Algorithmus, eine Neuplanung Algorithmus basiert auf Einer*. Es benötigt die Fähigkeit, Sie zu entfernen aus der Mitte der priority-queue.
Im Allgemeinen, Sie wollen post eine neue Frage gestellt, anstatt neue Fragen hinzufügen, um einen vier Jahre alten post. Aber um Ihre Fragen zu beantworten: 1) In einem standard-Binär-heap O(log n) ist der optimale Komplexität. 2) Löschen aus der Mitte des Haufens wird nie teurer sein, als das löschen der root-Knoten, und dass die operation bereits bewiesen, in O(log n). O(log n) ist die worst-case die Komplexität für das löschen eines Knoten irgendwo in den heap. Beachten Sie jedoch, dass das, was ich bereits in meiner ursprünglichen Antwort bleibt immer noch wahr: es dauert O(n) den Knoten zu löschen.
mathcs.emory.edu/~cheung/Kurse/171/Lehrplan/9-BinTree = /...

InformationsquelleAutor tesfa koli | 2012-01-02

  1. 79

    Eigentlich, können Sie ein Element aus der Mitte eines Haufens ohne Probleme.

    Die Idee, um das Letzte Element im heap und, ausgehend von der aktuellen position (d.h. die position, die das Element, das Sie gelöscht), sift es, wenn das neue Element größer ist als der Elternteil, der das alte Element. Wenn es nicht größer als die Eltern, dann sieben Sie es nach unten.

    Dass sich das Verfahren für einen max-heap. Für einen min-heap, natürlich, Sie würde umkehren die größer und weniger Fällen.

    Finden ein Element in einem heap ist O(n) - operation, aber wenn Sie bereits wissen, wo es ist, in den Haufen, es zu entfernen ist O(log n).

    Veröffentlichte ich eine heap-basierte priority queue für DevSource ein paar Jahre zurück. Sehen Eine Priority-Queue-Implementierung in C#. Es hat eine RemoveAt Methode, die macht genau das, was ich beschrieben habe.

    Vollständige Quelle bei http://www.mischel.com/pubs/priqueue.zip

    Update

    Einige haben gefragt, ob es möglich ist, sich zu bewegen, nachdem er den letzten Knoten in den heap zum ersetzen des gelöschten Knotens. Betrachten Sie diese heap:

            1
    6       2
  7   8   3

    Wenn Sie löschen den Knoten mit dem Wert 7 den Wert 3 ersetzt:

            1
    6       2
  3   8

    Haben Sie jetzt, um es zu bewegen, um einen gültigen heap:

            1
    3       2
  6   8

    Der Schlüssel hier ist, dass, wenn das Element, das Sie ersetzen in einem anderen Teilbaum als das Letzte Element im heap, es ist möglich, dass die Ersatz-Knoten kleiner als die Eltern des zu ersetzenden Knoten.

    Ich bin mir nicht ganz sicher, ich verstehe Sie. Sind Sie sagen, dass wir entfernen beliebiger Elemente und ersetzen Sie Ihre position mit dem letzten element des Heaps Baum, und entweder sift oben oder unten? Ich bezweifle, dass das was du sagst, weil 1) Es können sieben bis je 2) Der Baum ist möglicherweise nicht vollständig mehr... Kannst du das etwas erläutern? Danke.
    Das ist genau das, was ich sage. Und es funktioniert in der Tat. Werfen Sie einen Blick auf mein Beispiel-code oder schauen Sie auf heap-Implementierung, ermöglicht die Entfernung.
    Es kann tatsächlich zu sichten, weil es möglicherweise nicht Teil der gleichen Struktur. Bild der Wurzel-an den Anfang der Baum ist aufgeteilt in zwei unabhängige Teile. Man könnte das löschen von Knoten aus dem linken Teilbaum, aber wenn Sie das Letzte Element aus der letzten Ebene des Heaps, die möglicherweise ein Element vom rechten Teilbaum. Es ist nicht der Bestellung zwischen den unterstrukturen, nur im Verhältnis zu Ihren Eltern.
    ist eine Verschiebung nach oben möglich, einen Wert für das Letzte element nach dem austauschen? auch indeces sind meist weniger verwendet für die Haufen, wie Sie sich Häufig ändert, während Sie Sie Eindrücken und poping. was wäre die Strategie zum löschen von Wert?
    Wenn Sie löschen möchten, indem Sie Wert, Sie aufrecht zu erhalten, ein dictionary oder hash map, sortiert nach Wert, enthält den index des Elements im heap. Und, ja, es ist möglich, einen Wert zu verschieben bis nach dem vertauschen. Siehe mein update.

    InformationsquelleAutor Jim Mischel

  2. 15

    Das problem mit dem entfernen eines beliebigen Elements aus einem heap ist, dass Sie können es nicht finden.

    In einem Haufen auf der Suche nach einem beliebigen element ist O(n) so entfernen Sie ein element [wenn von Wert] ist O(n) als gut.

    Wenn es für Sie wichtig, zu entfernen beliebiger Elemente bilden die Datenstruktur heap ist wahrscheinlich nicht die beste Wahl, sollten Sie überlegen, voll mit sortierten Daten Strukturen statt wie ausgewogene BST oder eine skip-Liste.

    Wenn Ihr element ist gegeben durch den Hinweis, es ist jedoch möglich, um es zu entfernen in O(logn) indem Sie einfach 'austauschen' es mit dem letzten Blatt [erinnere mich an ein heap implementiert eine vollständige binäre Baum, so gibt es ein letztes Blatt, und Sie wissen genau, wo es ist], entfernen Sie diese element-und re-heapify die relevanten sub-heap.

    Beachten Sie, dass Sie es finden können, wenn Sie bereit sind, Rollen Sie Ihre eigenen heap-Implementierung. Sie brauchen nur es, um eine Zuordnung von Objekt zu indizieren, oder um intrusively speichern der index auf das Objekt und aktualisieren Sie es jedes mal, es swaps Elemente. Die Aktualisierung ist nicht teuer, da es immer nur auf einen swap, wo Sie nur die swap-Indizes, die Sie nicht haben, tun Sie das scanning.

    InformationsquelleAutor amit

  3. 2

    Wenn Sie ein max-heap, die Sie implementieren können dies durch die Zuweisung eines Wertes der größer ist als alle anderen (zB etwas wie int.MaxValue oder inf in welcher Sprache Sie verwenden) nicht möglich ist, das Element gelöscht, dann neu-heapify und es wird die neue Wurzel. Dann führen Sie eine regelmäßige Entfernung von dem root-Knoten.

    Dadurch wird ein weiteres re-heapify, aber ich kann nicht sehen, eine offensichtliche Weg, um zu vermeiden, tun Sie es zweimal. Dies deutet darauf hin, dass vielleicht ein heap ist nicht geeignet für Ihren Gebrauch-Fall, wenn Sie brauchen, um pull-Knoten von der Mitte des es oft.

    (für einen min-heap, können Sie natürlich verwenden int.MinValue oder -inf oder was auch immer)

    InformationsquelleAutor rejj

  4. 1

    Was Sie erreichen wollen, ist nicht ein typischer heap-operation, und es scheint mir, dass, sobald Sie einführen "löschen" mittleren Elements" als eine Methode, die einige andere binäre Baum(z.B. rot-schwarz-oder AVL-Baum) ist eine bessere Wahl. Sie haben ein rot-schwarz-Baum implementiert, in einigen Sprachen(zum Beispiel Karte und setzen Sie in c++).

    Sonst den Weg zum mittleren element löschen ist, wie vorgeschlagen, in rejj Antwort: weisen Sie einen großen Wert(max-heap) oder kleinen Wert(für min-heap), um das element, sieben Sie es, bis es root und dann löschen.

    Dieser Ansatz hält immer noch die O(log(n)) Komplexität für mittlere element löschen, aber die, die Sie vorschlagen, nicht. Es haben Komplexität O(n*log(n)) und daher nicht sehr gut.
    Hoffe, das hilft.

    InformationsquelleAutor Ivaylo Strandjev

Schreibe einen Kommentar