Elternindex im binären Heap

Ein in einem Array abgelegter binärer Heap trägt Prioritätswarteschlangen, Heapsort und viele Kürzeste-Wege-Umsetzungen. Jedes Lehrbuch nennt eine Elternformel, doch die beiden Nummerierungskonventionen weichen um eins ab, und ein Versatz um eins zerstört still das Sift-up. Dieser Elternindex-Rechner nimmt den Arrayindex eines Knotens und die Nummerierung entgegen — nullbasiert mit Wurzel am Index null, oder einsbasiert mit Wurzel am Index eins — und liefert den Elternknoten über die passende geschlossene Form. Nullbasierte Heaps setzen Eltern gleich dem Abrunden von Index minus eins durch zwei. Einsbasierte Heaps setzen Eltern gleich dem Abrunden von Index durch zwei. Die Wurzel hat keinen Elternknoten und wird zurückgewiesen, statt einen negativen oder Scheinplatz zu erfinden.

Elternformeln bei nullbasierter und einsbasierter Nummerierung

Ein im Array ausgelegter binärer Heap speichert niemals Zeiger auf Eltern oder Kinder. Der Weg von einem Knoten zu seinem Elternknoten ist eine geschlossene Indexformel, und diese Formel hängt davon ab, ob das Array bei null oder bei eins zählt.

In der nullbasierten Konvention, die C, Java, JavaScript, Python und die meisten Produktionsheaps nutzen, sitzt die Wurzel am Index null, die Kinder von Knoten i stehen bei zwei i plus eins und zwei i plus zwei, und der Elternknoten eines Nicht-Wurzelknotens ist das Abrunden von i minus eins geteilt durch zwei.

In der einsbasierten Konvention vieler Lehrbücher, von CLRS-artigem Pseudocode und mancher Wettbewerbsschablone sitzt die Wurzel am Index eins, die Kinder stehen bei zwei i und zwei i plus eins, und der Elternknoten ist einfach das Abrunden von i geteilt durch zwei. Beide Identitäten sind für ganzzahlige Indizes exakt; sie sind weder Näherungen noch austauschbar. Dieser Rechner wendet die passende Identität an, nachdem Sie die Konvention gewählt haben, und weist die Wurzel zurück, weil die Wurzel keinen Elternknoten hat.

Die beiden Konventionen zu verwechseln ist der klassische Versatz um eins: ein Sprach-Array wie einsbasiert oder ein Lehrbuchdiagramm wie nullbasiert zu behandeln liefert einen Elternknoten einen Platz neben der Wahrheit und zerbricht still Sift-up sowie Decrease-key.

Eingabevertrag, Antwortform und Fehlerverhalten

Steht indexing auf zero, muss der Index mindestens null sein; steht indexing auf one, muss der Index mindestens eins sein. Die Wurzel der gewählten Konvention — null in einem nullbasierten Heap, eins in einem einsbasierten Heap — wird mit einer Meldung zurückgewiesen, die diese Wurzel nennt, denn einen Elternknoten bei minus eins zu erfinden oder auf den letzten Platz zu wickeln wäre eine Lüge. Beispiel: Index fünf mit der standardmäßigen nullbasierten Konvention liefert Eltern zwei, weil das Abrunden von vier durch zwei zwei ergibt.

Beispiel: Index vier mit einsbasierter Nummerierung liefert Eltern zwei, während dieselbe Vier in einem nullbasierten Heap Eltern eins hätte — dieses Paar ist der ganze Grund, warum die Konvention ein Feld ist. Gescheiterte Prüfung wird nicht berechnet.

Wo ein Elternindex-Rechner seinen Nutzen zeigt

Interviewvorbereitung, Algorithmuskurse und produktive Prioritätswarteschlangen brauchen denselben Aufstieg zum Elternknoten und widersprechen sich bei der Nummerierung. Wer eine Sift-up-Spur prüft, will bestätigen, dass der Elternknoten von fünf in einem Sprach-Array zwei ist und der Elternknoten von vier auf einem einsbasierten Blatt zwei ist, ohne die Formel in jedem Schritt von Hand umzudrehen. Autobewerter für Strukturhausaufgaben brauchen ein deterministisches Orakel, das die Wurzel als elternlos zurückweist, statt ein stilles Minus-eins zurückzugeben, das eine fehlerhafte Abgabe als Erfolg werten könnte.

Wer einen Lehrbuchheap in eine nullbasierte Sprache überträgt, oder umgekehrt, kann beide Konventionen in Tests festnageln und den Versatz um eins vor der Auslieferung fangen. Visualisierer und Wettbewerbgerüste, die den Baum aus einem Array zeichnen, können den Elternknoten jedes Nicht-Wurzelplatzes erfragen und Kanten legen, ohne zwei Kopien der Formel einzubetten. Halten Sie Anfragen klein, nageln Sie die Elternganzzahl in Tests fest, und Sie erhalten wiederholbare Aufstiege für Hausaufgaben, LMS-Erweiterungen und Rand-Worker, ohne eine eigene Heap-Bibliothek aufzubauen.