Elemente in binäre Min-Heaps einfügen

7

Wenn ich Elemente: 10,12,14,1,6 in einen binären Min-Heap ein Element nach dem anderen einfügen würde, wie würden die Ergebnisse aussehen, ist mein Problem mit dem folgenden

Wenn ich anfange, habe ich:

%Vor%

dann

%Vor%

dann

%Vor%

dann

%Vor%

Aber das ist nicht richtig, also was ist der richtige Weg?

Hinweis: Dies ist eine Hausaufgabenfrage, ich versuche das Konzept zu verstehen, wenn Sie sich bei der Lösung der Frage nicht wohl fühlen (es ist sowieso nicht die ganze Frage), geben Sie bitte ein Beispiel mit ähnlichem Thema an.

    
user220755 19.01.2010, 11:44
quelle

2 Antworten

17

Sie müssen das neue Element als Kind (oder Blatt genau) zum Heap (nicht als root) hinzufügen, das heißt, Sie müssen es an der ersten "richtigen" freien Stelle (oder in Ihrem Heap-Array, nur bei das Ende).

Dann müssen Sie die Heap-Bedingungen wiederherstellen, das heißt "heapify". Dies geschieht in zwei Phasen:

  1. Wiederholt das neue Element (allgemein: das Element, das gegen die Heap-Bedingungen verstößt) mit seinem Elternknoten austauschen, solange es kleiner ist als das Elternelement und nicht das Stammverzeichnis.
  2. Tauschen Sie das neue Element wiederholt mit dem Kind mit dem kleinsten Wert aus, bis das neue Element zu einem Leave wird oder beide Kindknoten größer als das Element selbst sind.

Das bedeutet

%Vor%

+ 1 führt zu

%Vor%

Und das verstößt gegen die Heap-Bedingungen, also müssen Sie

kopieren %Vor%

Aber das ist immer noch nicht richtig, also musst du es erneut haufen

%Vor%

Und da bist du ... alles in Ordnung jetzt: -)

    
Leo 19.01.2010, 12:10
quelle
2
%Vor%     
Fred 13.01.2012 23:59
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Was bedeutet using (object obj = new Object ())?