Dúvida:
Para ordenar arrays com heapsort, costuma-se simular neles árvores com até dois filhos por pai, não mais. Minha dúvida é se há estudos, implementações, experimentos, relatórios, dados acessíveis que investigam o desempenho do heapsort em arrays simulando árvores com números maiores de filhos por pai.
Detalhes:
Eu implementei a ordenação de array com heapsort usando o máximo de dois filhos por pai. Com as noções de complexidade de código que tenho, me pareceu que o número de comparações de uma interação do heapsort (definição do último elemento do subarray atual) fica, no pior caso, em torno de 2*log2(n)
, pois são duas comparações por nível de profundidade e a profundidade fica em torno de log2(n)
. Mas e se eu "adotasse mais filhos"?
Pensando nisso, suponho que possamos adaptar o código para mais de dois filhos adicionando, para cada filho adicional, uma comparação por nível de profundidade. Aumenta as comparações por profundidade, mas a profundidade diminui, assim talvez realizando menos comparações. A fórmula que encontrei para estimar as comparações por interação dependendo do número F
de filhos é F*logF(n)
.
Se eu estiver certo, matematicamente o ideal seria F = e ~ 2.71828
, mas não dá. Aumentar de dois filhos para três filhos diminuiria o número de comparações (-5,36%
em F=3
). Aumentar de dois para quatro filhos, conservaria (0,00%
em F=4
). Aumentar de dois para cinco filhos ou mais aumentariam as comparações (+7,67%
se F=5
). Enfim, matematicamente é assim, mas como é o desempenho na prática? Já se testou isso? Há dados conhecidos?
O(log3(n))
eO(log2(n))
são assintoticamente equivalentes. Que de certa forma estou a dizer o que o @JeffersonQuesado disse mas de outra forma.