Estrutura de dados de um d-heap [RESOLVIDO]

1. Estrutura de dados de um d-heap [RESOLVIDO]

Lucas
DcoderLA

(usa Debian)

Enviado em 18/07/2021 - 17:32h

Boa tarde pessoal, tudo bem ?

Estou tentando entender d-heap para filas de prioridade, mas no momento estou empacado em saber como seria a estrutura de uma d-heap. Sei que uma heap padrão é binaria, então seguiria as estrutura de uma arvore binaria, mas para o caso de um d >= 3, como seria a estrutura ? Qualquer dica é válida.

Desde já agradeço.


  


2. MELHOR RESPOSTA

Paulo
paulo1205

(usa Ubuntu)

Enviado em 20/07/2021 - 00:45h

Você pode pensar em termos de árvore, mas a implementação de heaps geralmente usa arrays. Cada nível n (n>=0) da árvore possui no máximo d^n (d elevado a n) nós, e o índice no array para o primeiro de cada nível elementos começa no índice (1-d^n)/(1-d). Se você estiver varrendo o d-heap, sabe que nó com índice k é filho do nó com índice (int)((k-1)/d) e que os nós filhos terão índices que vão de k*d+1 até (k+1)*d.


... Então Jesus afirmou de novo: “(...) eu vim para que tenham vida, e a tenham plenamente.” (João 10:7-10)