Ich muss das zweitgrößte Element in einem Min - Heap - Array finden.Bereich des zweitgrößten Schlüssels in Min - Heap
Nun, ich erkannte, dass es eines der Blätter des Baumes oder ein Elternteil eines Blattes sein kann. Ich kam zu dem Schluss, dass der Bereich dieser Knoten - [floor (n/4) + 1, n] ist. Aber trotzdem kann ich einige Bäume bauen, die nicht mit dieser Formel übereinstimmen.
Vielen Dank für Ihre Hilfe!
Mein Kommentar berücksichtigte die mögliche Existenz von doppelten Elementen im Heap nicht. Wenn doppelte Elemente möglich sind, kann der zweitgrößte Knoten jeder Knoten im Heap sein, mit Ausnahme des letzten Knotens.
Fehlende doppelte Elemente, dann befindet sich der nächst größere Knoten entweder auf der Blattebene, oder er ist ein Knoten auf der Ebene direkt über der Blattebene und hat höchstens ein Kind. Es könnte keine Kinder haben.
Der erste Knoten, der könnte der vorletzte ist bei 2^(h-2) + 1, wo h ist die Höhe des Baumes. Vereinbarungsgemäß hat ein Baum mit einem Wurzelknoten lediglich eine Höhe von 0, so gegeben, diese heap:
0
/ \
1 2
/\ /\
3 4 5 6
Der Baum mit einer Höhe von 2 weist der erste Knoten, der zweite sein könnte größten bei 2^(2-2)+1 ist, oder 1.
Der Bereich der Knoten, die den vorletzten Wert enthalten könnten, lautet dann [2^(h-2) + 1, n-1].
Bei den obigen Annahmen wird davon ausgegangen, dass der Stamm Ihres Heapspeichers in Ihrem Array den Index 0 hat. Wenn der Stamm den Index 1 hat, müssen Sie entsprechend anpassen.
Nein, der zweitgrößte Knoten * muss * ein Blatt oder Elternteil eines Blattes sein. Und es kann nur das Elternteil eines Blattes sein, wenn der Baum nicht voll ist. Wenn Sie ein Beispiel für einen gültigen Min-Heap haben, in dem der zweitgrößte Knoten kein Blatt oder Elternteil eines Blattes ist, schreiben Sie es bitte. –
Ok, also brauche ich eine Formel von n bis zum letzten Elternteil mit einem Kind oder wenn der Baum von n bis zum letzten Blatt voll ist, oder? –