Índice padre de un heap binario

Un heap binario guardado en un arreglo es la estructura que sostiene las colas de prioridad, el heapsort y muchas implementaciones de camino más corto. Todo manual enumera una fórmula del padre, pero las dos convenciones de indexación discrepan en una unidad, y un desfase de uno corrompe en silencio el sift-up. Esta calculadora del índice del padre acepta el índice de arreglo de un nodo y la convención de numeración — basada en cero, con la raíz en el índice cero, o basada en uno, con la raíz en el índice uno — y devuelve el padre con la forma cerrada que corresponde. Los heaps basados en cero usan padre igual al piso de índice menos uno entre dos. Los heaps basados en uno usan padre igual al piso de índice entre dos. La raíz no tiene padre y se rechaza en lugar de inventar una ranura negativa o ficticia.

Fórmulas del padre con indexación desde cero y desde uno

Un heap binario dispuesto en un arreglo jamás almacena punteros al padre ni a los hijos. El recorrido desde un nodo hasta su padre es una fórmula de índice en forma cerrada, y esa fórmula depende de si el arreglo se numera desde cero o desde uno.

En la convención basada en cero que usan C, Java, JavaScript, Python y la mayoría de heaps de producción, la raíz ocupa el índice cero, los hijos del nodo i quedan en dos i más uno y dos i más dos, y el padre de un nodo que no es raíz es el piso de i menos uno dividido entre dos.

En la convención basada en uno que usan muchos manuales, el seudocódigo al estilo CLRS y algunas plantillas de concurso, la raíz ocupa el índice uno, los hijos quedan en dos i y dos i más uno, y el padre es sencillamente el piso de i dividido entre dos. Ambas identidades son exactas para índices enteros; no son aproximaciones ni son intercambiables. Esta calculadora aplica la identidad que corresponde después de que usted elija la convención, y rechaza la raíz porque la raíz no tiene padre.

Confundir las dos convenciones es el clásico error de uno: tratar un arreglo de lenguaje como si partiera de uno, o un diagrama de libro como si partiera de cero, produce un padre a una ranura de la verdad y rompe en silencio el sift-up y el decrease-key.

Contrato de entrada, forma de la respuesta y errores

Cuando indexing es zero el índice debe ser al menos cero; cuando indexing es one el índice debe ser al menos uno. La raíz de la convención elegida — cero en un heap basado en cero, uno en un heap basado en uno — se rechaza con un mensaje que nombra esa raíz, porque inventar un padre en menos uno o envolver hasta la última ranura sería mentir.

Ejemplo: índice cinco con la convención basada en cero por omisión produce padre dos, porque el piso de cuatro entre dos es dos. Ejemplo: índice cuatro con indexación basada en uno produce padre dos, mientras que el mismo cuatro en un heap basado en cero tendría padre uno — ese par es toda la razón de que la convención sea un campo. La validación fallida no se factura.

Dónde aporta valor una calculadora del índice del padre

La preparación de entrevistas, los cursos de algoritmos y las colas de prioridad de producción necesitan el mismo recorrido hacia el padre, y discrepan en la numeración. Quien revisa un trazo de sift-up quiere confirmar que el padre de cinco es dos en un arreglo de lenguaje y que el padre de cuatro es dos en una hoja basada en uno, sin invertir la fórmula a mano en cada paso.

Los calificadores automáticos de deberes de estructuras necesitan un oráculo determinista que rechace la raíz por no tener padre, en lugar de devolver un menos uno silencioso que un envío defectuoso podría tratar como acierto. Quien porta un heap de libro a un lenguaje basado en cero, o al revés, puede fijar ambas convenciones en las pruebas y cazar el desfase de uno antes de publicar.

Los visualizadores y andamiajes de concurso que dibujan el árbol desde un arreglo pueden pedir el padre de cada ranura que no es raíz y trazar aristas sin incrustar dos copias de la fórmula. Mantenga las peticiones modestas, fije el entero padre en las pruebas y obtendrá recorridos reproducibles para deberes, complementos LMS y workers en el borde sin montar una biblioteca local de heaps.