heap binário vs heap binomial vs heap fibonacci, em relação ao desempenho para uma fila de prioridade
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Alguém poderia me explicar como devo decidir se devo usar uma ou outra implementação de heap, entre as mencionadas no título?
Gostaria de uma resposta que me orientasse na escolha da implementação quanto ao desempenho da estrutura, de acordo com o problema.No momento, estou fazendo uma fila de prioridades, mas gostaria de saber não apenas a implementação mais adequada para este caso, mas o básico que me permite escolher uma implementação em qualquer outra situação ...
Outra coisa a considerar é que estou usando haskell desta vez, então, se você souber de algum truque ou algo que possa melhorar a implementação com esta linguagem, por favor me avise!mas, como antes, comentários sobre o uso de outros idiomas também são bem-vindos!
Obrigado!e desculpe se a pergunta é muito básica, mas eu não estou familiarizado com o heaps.É a primeira vez que enfrento a tarefa de implementar um ...
Obrigado novamente!
Solução
Você pode encontrar o terceiro artigo em http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf relevante.
Outras dicas
Em primeiro lugar, você não implementará um heap padrão em Haskell. Em vez disso, você implementará um heap persistente e funcional . Às vezes, as versões funcionais das estruturas de dados clássicas têm o mesmo desempenho do original (por exemplo, árvores binárias simples), mas às vezes não (por exemplo, filas simples). No último caso, você precisará de uma estrutura de dados funcional especializada.
Se você não está familiarizado com estruturas de dados funcionais, sugiro começar com o excelente livro ou tese (capítulos de juros: pelo menos 6.2.2, 7.2.2).
Se tudo isso passou pela sua cabeça, sugiro começar com a implementação de um heap binário vinculado simples. (Fazer um heap binário baseado em array eficiente em Haskell é um pouco tedioso.) Uma vez feito isso, você pode tentar implementar um heap binomial usando o pseudocódigo de Okasaki ou mesmo começando do zero.
Eles têm complexidade de tempo diferente em operações diferentes na Fila de prioridade. Aqui está uma tabela visual para você
╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║ Operation ║ Binary ║ Binomial ║ Fibonacci ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ insert ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ find Min ║ O(1) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Revmove ║ O(logN) ║ O(logN) ║ O(logN) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Decrease Key ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Union ║ O(N) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║ ║ ■ Heap height = logN ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min. ║
║ ║ ║ ■ Height = k. ║ (keeps find min/max O(1)) ║
║ ║ ║ ■ Degree of root = k. ║ ■ Set of marked nodes. ║
║ Useful ║ ║ ■ Deleting root yields ║ (keep the heaps flat) ║
║ Properties ║ ║ binomial trees ║ ║
║ ║ ║ Bk-1, … , B0. ║ ║
║ ║ ║ (see graph below) ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝
Consegui essa imagem nos slides da aula de Princeton
Pilha binomial:
Fibonacci Heap:
Observação: Binomial e Fibonacci Heap parecem familiares, mas são sutilmente diferentes:
- Heap binomial: consolide rapidamente as árvores após cada inserção.
- heap de Fibonacci: preguiçosamente adie a consolidação até o próximo minuto de exclusão.
Algumas referências ao heap binomial funcional, heap de Fibonacci e heap de emparelhamento: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Se o desempenho for realmente o problema, sugiro usar a pilha de emparelhamento.O único risco é que seu desempenho ainda seja uma conjectura até agora.Mas os experimentos mostram que o desempenho é muito bom.
