Max und Min Heap mit den gleichen Elementen

Question

Betrachten Sie das folgende Beispiel. Ich füge Zufallszahlen zum Min-Heap hinzu und füge gleichzeitig die gleichen Zahlen in der gleichen Reihenfolge zum Max-Heap hinzu. Am Ende werden diese 2 Haufen die gleichen Zahlen haben mit dem Unterschied, dass einer min Heap und der zweite Max Heap ist.

Jetzt ist hier die Frage:

Wenn ich mich entscheide das maximale Element von max Haufen zu entfernen, wird das maximale Element von max Heap immer am unteren Rand des min Haufen? Wenn nicht, dann ist eine andere Frage, dass, wenn ich dieses Max-Element aus dem Min-Heap mit dem letzten Element von Min-Heap entfernen und das letzte Element löschen möchte, ich jemals eine Operation ausführen müsste, die dieses geschaltete Element vergleichen müsste mit seinem Kind, um min Heap zu reparieren? Oder wird es immer der Fall sein, es mit dem Elternteil zu vergleichen, um min heap zu beheben?

Answer 1

Nach Definition eines Max Heap ist der Stamm immer größer als seine Kinder. Es gibt jedoch keine spezifische Anordnung unter Kindern, so dass das linke Kind nicht immer größer ist als das rechte und umgekehrt. Das Max-Element von Max-Heap, das die Wurzel ist, muss sich auf einem Blatt im Min-Heap befinden. Wir wissen nicht, welches Blatt, das hängt von der Konfiguration der Elemente ab. (dh die Reihenfolge, in der diese Elemente eingefügt werden, da normalerweise Elemente eingefügt werden, die von ganz links bis zur äußersten rechten Seite des Baums gefüllt werden)