!!
Nehmen wir an dass wir den folgenden Heap haben:
Wenn wir den folgenden Algorithmus anwenden
HeapInsert(HeapTable A, int size, Key K, Type I) {
if (size == N) then error; /* Heap is full */
m = size;
while (m > 0 and K < Α[floor((m-1)/2)]->Key) {
Α[m]->key = Α[floor((m-1)/2)]->Key;
Α[m]->data = Α[floor((m-1)/2)]->data; /
}
Α[m]->Key = K;
Α[m]->data = I;
size++;
}
bekommen wir folgendes:
Ich will die Funktion HeapInsert nochmal schreiben sodass sie von oben nach unten durchgeführt wird.
Die Funktion soll entsprechende Swaps von Schlüsseln machen beim Überqueren von Knoten, von der Wurzel zu den Knoten, der der Vaterknoten des neu eingefügten Knoten sein wird.
Diese Maßnahmen sollten durchgeführt werden, so dass der neu eingefügte Knoten nach dem Einsetzen der ganz rechte Blatt ist und dass keine weiteren Aktionen (beispiels Swaps) nach der Platzierung des neuen Knotens im Array, der den Heap implementiert benötigt werden.
Die Funktion sollte Zeitkomplexität O(logm) haben, und die Eigenschaften eines Heaps sollten erhalten sein.
Also müssen wir einen neuen Knoten kreieren der das ganz rechte Kind vom letzten Knoten der vorletzten Ebene sein wird und danach seinen Schlüssel mit dem seines Vaterknoten vergleichen und wenn es kleiner ist die Werte austauschen und die gleiche Prozedur weitermachen bis wir einen kleineren Schlüssel finden oder die Wurzel erreichen?
