Índice pai de um heap binário

Um heap binário guardado em um vetor é a estrutura por trás de filas de prioridade, heapsort e muitas implementações de caminho mais curto. Todo livro lista uma fórmula do pai, mas as duas convenções de indexação discordam em uma unidade, e um desvio de um corrompe em silêncio o sift-up. Esta calculadora do índice do pai aceita o índice de vetor de um nó e a convenção de numeração — baseada em zero, com a raiz no índice zero, ou baseada em um, com a raiz no índice um — e devolve o pai com a forma fechada correspondente. Heaps baseados em zero usam pai igual ao piso de índice menos um sobre dois. Heaps baseados em um usam pai igual ao piso de índice sobre dois. A raiz não tem pai e é recusada em vez de inventar um slot negativo ou fictício.

Fórmulas do pai com indexação a partir de zero e de um

Um heap binário disposto em um vetor jamais armazena ponteiros para o pai ou para os filhos. O caminho de um nó até o pai é uma fórmula de índice em forma fechada, e essa fórmula depende de o vetor ser numerado a partir de zero ou a partir de um.

Na convenção baseada em zero usada por C, Java, JavaScript, Python e a maior parte dos heaps de produção, a raiz ocupa o índice zero, os filhos do nó i ficam em dois i mais um e dois i mais dois, e o pai de um nó que não é raiz é o piso de i menos um dividido por dois.

Na convenção baseada em um usada por muitos livros, o pseudocódigo no estilo CLRS e alguns gabaritos de competição, a raiz ocupa o índice um, os filhos ficam em dois i e dois i mais um, e o pai é simplesmente o piso de i dividido por dois. As duas identidades são exatas para índices inteiros; não são aproximações e não são intercambiáveis. Esta calculadora aplica a identidade correspondente depois que você escolhe a convenção, e recusa a raiz porque a raiz não tem pai.

Confundir as duas convenções é o erro clássico de um: tratar um vetor de linguagem como se partisse de um, ou um diagrama de livro como se partisse de zero, produz um pai a um slot da verdade e quebra em silêncio o sift-up e o decrease-key.

Contrato de entrada, formato da resposta e erros

Quando indexing é zero o índice deve ser pelo menos zero; quando indexing é one o índice deve ser pelo menos um. A raiz da convenção escolhida — zero em um heap baseado em zero, um em um heap baseado em um — é recusada com uma mensagem que nomeia essa raiz, porque inventar um pai em menos um ou circular até o último slot seria mentir. Exemplo: índice cinco com a convenção baseada em zero por omissão produz pai dois, porque o piso de quatro sobre dois é dois.

Exemplo: índice quatro com indexação baseada em um produz pai dois, enquanto o mesmo quatro em um heap baseado em zero teria pai um — esse par é toda a razão de a convenção ser um campo. A validação falha não é cobrada.

Onde uma calculadora do índice do pai se paga

Preparação para entrevistas, cursos de algoritmos e filas de prioridade de produção precisam do mesmo percurso até o pai, e discordam na numeração. Quem confere um traço de sift-up quer confirmar que o pai de cinco é dois em um vetor de linguagem e que o pai de quatro é dois em uma folha baseada em um, sem inverter a fórmula à mão em cada passo.

Avaliadores automáticos de lição de estruturas precisam de um oráculo determinístico que recuse a raiz por não ter pai, em vez de devolver um menos um silencioso que um envio defeituoso poderia tratar como acerto. Quem porta um heap de livro para uma linguagem baseada em zero, ou o inverso, pode fixar as duas convenções nos testes e caçar o desvio de um antes de publicar.

Visualizadores e andaimes de competição que desenham a árvore a partir de um vetor podem pedir o pai de cada slot que não é raiz e traçar arestas sem embutir duas cópias da fórmula. Mantenha os pedidos modestos, fixe o inteiro pai nos testes e você obtém percursos reproduzíveis para lição de casa, plugins LMS e workers na borda sem montar uma biblioteca local de heaps.