Gewusst wie: löschen von ein Max-Heap?

Wenn wir 15 in der Wurzel, was wäre der Prozess von heapify?

            85
            /\
           / \
          /   \
        55      70
        /\      /\
       / \    / \
      22  33  30  65
     /\   /
   14 15 15

Was das sein soll Weg löschen 85 aus dem Heap?

  • tech-faq.com/deleting-an-element-from-a-heap.html
  • Warum nicht? 15 niedriger ist als 33, so dass die heap-Eigenschaft erfüllt ist.
  • OK. Meine Frage war nicht an diesem Punkt. Ich veränderte den Haufen. Versuchen Sie einfach zu löschen 85 und Sag mir, was passiert.
  • Hm, du hast Recht. Ich habe den binären Baum-Eigenschaft in Sie als gut.
  • Der Haufen ist ok. Die heap-Anwesen ist, dass jeder Elternteil größer ist dann seine Söhne. Dies ist nicht ein binary tree.
  • Ich Frage mich, wer von Ihnen positiv bewertet werden "dieser Baum ist nicht ein Haufen"

InformationsquelleAutor user366312 | 2011-07-10
  1. 4

    Als Sie immer tauschen es mit dem größeren der beiden (heap-Eigenschaft bedeutet, dass die Eltern immer größer, als seine Kinder):

                15
            /\
           / \
          /   \
        55      70
        /\      /\
       / \    / \
      22  33  30  65
     /\   
   14 15

            70
            /\
           / \
          /   \
        55      15
        /\      /\
       / \    / \
      22  33  30  65
     /\   
   14 15

            70
            /\
           / \
          /   \
        55      65
        /\      /\
       / \    / \
      22  33  30  15
     /\   
   14 15
    InformationsquelleAutor Femaref
  2. 1

    Wenn Sie löschen 85 und ersetzen Sie es mit 15, biegen Sie die semi-heap wieder zu einem heap durch downheaping, d.h. die 15 an der Wurzel "Waschbecken" auf dem Weg der größeren Kinder. In diesem Fall wird die swap-Partition mit 70 dann mit 65.

    Edit: weil wir immer vertauschen mit dem größeren Kind, ist es gewährleistet, dass wir am Ende mit einem gültigen heap (z.B. wenn wir tauschten unsere 15 mit 55 statt 70, hätten wir 70 als ein Kind mit 55 ist das nicht gut)

    InformationsquelleAutor
  3. 0

    Fügen Sie den neuen Wert als letztes (Recht auf 20 in deinem Beispiel) und dann versuchen zu beheben heap,, das ist zu vergleichen mit seinen Eltern, wenn es größer ist der swap und vergleichen Sie Sie erneut, bis kein swap benötigt wird (oder root)

    Um zu löschen, entfernen Sie Sie ersetzen das Letzte Objekt (15 in Sie Beispiel) an und fixieren Sie den heap nach unten.

    • Wenn ich 15 an der Wurzel und der Aufruf von heapify, 55 gehen sollte an der Wurzel. Aber was dann? 70 ist noch ein Kandidat für die erste Wurzel. Dann sollten wir heapify den rechten Teilbaum auch?
    • Nein, der größere der beiden wird getauscht. Also die 70 wird die neue Wurzel.
    • No. 55, sollte das nicht gehen, weil das bedeutet, dass die Eltern nicht größer ist, dann seine Söhne, die die Eigenschaft des Heaps.
    InformationsquelleAutor roni
Schreibe einen Kommentar