Indice padre di un heap binario

Un heap binario conservato in un array è la struttura dietro code di priorità, heapsort e molte implementazioni di cammino minimo. Ogni manuale elenca una formula del padre, ma le due convenzioni di indicizzazione discordano di un'unità, e uno scarto di uno corrompe in silenzio il sift-up. Questo calcolatore dell'indice padre accetta l'indice di array di un nodo e la convenzione di numerazione — a partire da zero, con la radice all'indice zero, oppure a partire da uno, con la radice all'indice uno — e restituisce il padre con la forma chiusa corrispondente. Gli heap a partire da zero usano padre uguale al pavimento di indice meno uno su due. Gli heap a partire da uno usano padre uguale al pavimento di indice su due. La radice non ha padre e viene rifiutata invece di inventare uno scomparto negativo o fittizio.

Formule del padre con indicizzazione da zero e da uno

Un heap binario disposto in un array non memorizza mai puntatori al padre né ai figli. La risalita da un nodo al proprio padre è una formula di indice in forma chiusa, e quella formula dipende dal fatto che l'array sia numerato da zero oppure da uno.

Nella convenzione a partire da zero usata da C, Java, JavaScript, Python e dalla maggior parte degli heap di produzione, la radice occupa l'indice zero, i figli del nodo i stanno in due i più uno e due i più due, e il padre di un nodo che non è radice è il pavimento di i meno uno diviso due.

Nella convenzione a partire da uno usata da molti manuali, dallo pseudocodice in stile CLRS e da alcuni modelli da concorso, la radice occupa l'indice uno, i figli stanno in due i e due i più uno, e il padre è semplicemente il pavimento di i diviso due. Entrambe le identità sono esatte per indici interi; non sono approssimazioni e non sono intercambiabili. Questo calcolatore applica l'identità corrispondente dopo che Lei ha scelto la convenzione, e rifiuta la radice perché la radice non ha padre.

Confondere le due convenzioni è il classico errore di uno: trattare un array di linguaggio come se partisse da uno, o un diagramma da manuale come se partisse da zero, produce un padre a uno scomparto dalla verità e rompe in silenzio il sift-up e il decrease-key.

Contratto di ingresso, forma della risposta ed errori

Quando indexing è zero l'indice deve essere almeno zero; quando indexing è one l'indice deve essere almeno uno. La radice della convenzione scelta — zero in un heap a partire da zero, uno in un heap a partire da uno — viene rifiutata con un messaggio che nomina quella radice, perché inventare un padre a meno uno o avvolgere fino all'ultimo scomparto sarebbe una menzogna. Esempio: indice cinque con la convenzione a partire da zero per omissione produce padre due, perché il pavimento di quattro su due è due.

Esempio: indice quattro con indicizzazione a partire da uno produce padre due, mentre lo stesso quattro in un heap a partire da zero avrebbe padre uno — quella coppia è l'intera ragione per cui la convenzione è un campo. La convalida fallita non viene fatturata.

Dove un calcolatore dell'indice padre merita il proprio posto

La preparazione ai colloqui, i corsi di algoritmi e le code di priorità di produzione hanno bisogno della stessa risalita verso il padre, e discordano sulla numerazione. Chi verifica una traccia di sift-up vuole confermare che il padre di cinque è due in un array di linguaggio e che il padre di quattro è due su un foglio a partire da uno, senza invertire la formula a mano a ogni passo.

I correttori automatici dei compiti di strutture servono un oracolo deterministico che rifiuti la radice perché non ha padre, invece di restituire un meno uno silenzioso che un invio difettoso potrebbe trattare come successo. Chi porta un heap da manuale in un linguaggio a partire da zero, o il contrario, può fissare entrambe le convenzioni nei test e cogliere lo scarto di uno prima della pubblicazione.

I visualizzatori e le impalcature da concorso che disegnano l'albero da un array possono chiedere il padre di ogni scomparto non radice e tracciare gli archi senza incorporare due copie della formula. Tenga le richieste modeste, fissi l'intero padre nei test e otterrà risalite riproducibili per compiti, plugin LMS e worker al bordo senza allestire una biblioteca locale di heap.