Wie erstelle ich einen Heap?

Option 1 ist richtig .. Weil wir beginnen, ein untergeordnetes Element vom linken Knoten hinzuzufügen, und wenn das übergeordnete Element niedriger als das neu hinzugefügte untergeordnete Element ist, ersetzen wir sie. Und so wird es weitergehen, bis das Kind den Elternteil mit einem Wert größer als es bekommen hat.

Dein anfänglicher Baum ist

Nun fügen Sie 55 gemäß der Regel auf der linken Seite hinzu.

Aber Sie sehen, 22 ist niedriger als 55, also ersetzt es.

55 ist jetzt das Kind von 50, das immer noch unter 55 ist, also ersetzt sie auch.

Jetzt kann es nicht mehr sortiert werden, weil 77 größer als 55 ist ... SO ist Ihre Option 1 richtig.

Hier können Sie das Beispiel der Heap-Sortierung im Detail sehen. Dieser Link gibt an Ein Heap ist eine spezialisierte baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt: Wenn B ein Kindknoten von A ist, dann Schlüssel (A) ≥ Schlüssel (B). Dies bedeutet, dass sich ein Element mit dem größten Schlüssel immer im Wurzelknoten befindet. Daher wird ein solcher Heap manchmal auch als Max-Heap bezeichnet. (Wenn umgekehrt der Vergleich umgekehrt wird, befindet sich das kleinste Element immer im Wurzelknoten, was zu einem Min-Heap führt.) Es gibt keine Beschränkung hinsichtlich der Anzahl der untergeordneten Knoten in einem Heap, obwohl in der Praxis jeder Knoten dies hat höchstens zwei.

Viel Glück

Option 1, per Definition ist die Form des binären Heaps ein vollständiger Binärbaum. Die anderen 2 sind keine vollständigen Binärbäume. Siehe Ссылка

Die richtige Option ist 1.

Warum?

Denken Sie daran, dass eine Eigenschaft eines Heaps ein vollständiger binärer Baum sein soll, dh alle Ebenen, außer möglicherweise die letzte, sind vollständig gefüllt, und alle Knoten sind so weit wie möglich links ... wikipedia?

In den Optionen 2 und 3 wird das Element nicht so weit links wie möglich eingefügt, und daher ist die Eigenschaft des vollständigen Binärbaums gebrochen.

In Bezug auf die endgültige Position des Elements ist, indem das eingefügte Element (Sohn) mit seinem direkten Vorfahren (Vater) ausgetauscht wird, während der Sohn kleiner ist als der Vater.

Ich hoffe, das ist nützlich.