Eu sei como um heap min e max funciona, mas estou confuso sobre o que é uma fila de prioridades e como ela difere. Qualquer ajuda seria muito apreciada.
Respostas:
1 para resposta № 1Eles são a mesma coisa, apenas nomes diferentes.
A fila prioritária é implementada com mais eficiênciausando um heap e, em seguida, é um heap. Alguém poderia argumentar que a fila de prioridades poderia ser implementada com outras estruturas de dados (com menos eficiência).
Então, realisticamente eu vou dizer que eles são o mesmo.
Espere alguém ser pedante e dizer que um é um tipo abstrato, etc.
1 para resposta № 2
Fila de prioridade é um tipo de dados abstrato (uma definição de interface) que define três operações: está vazia, insert_with_prioritye pull_highest_priority_element. A definição diz o que essas funções devem fazer, mas não diz como deve ser implementado.
UMA heap binário é uma maneira de implementar uma fila de prioridades. Suas vantagens são a facilidade de implementação e isso é razoavelmente eficiente. Não é necessariamente a maneira mais eficiente de implementar uma fila de prioridades (veja abaixo). Considerando que um heap é definitivamente uma fila de prioridade, de maneira nenhuma é verdade que uma fila de prioridade é um heap.
Um heap geralmente implementa mais funcionalidadedo que é requerido por uma fila de prioridade. Por exemplo, os heaps normalmente têm um construtor que construirá a estrutura de dados interna muito rapidamente, sem precisar chamar inserir método para cada item. Heap também geralmente implementa um olhadinha método, que retornará o primeiro item, sem removê-lo. Ambas estas funções não fazem parte da definição da fila de prioridade.
Você pode implementar uma fila de prioridade com umlista simples não classificada, mas isso não seria particularmente eficiente. O mesmo com uma lista ordenada. Você também pode usar uma árvore de pesquisa binária balanceada, que lhe dará melhor desempenho que uma lista, mas não tão boa quanto um heap binário.
Há muitas implementações de filas de prioridade que são chamadas de "heaps", mas compartilham muito pouco em comum com o heap binário tradicional. Pilha de emparelhamento, por exemplo, é teoricamente mais eficiente do que o heap binário, como é Pilha de Fibonacci. Na prática, o heap de emparelhamento é mais eficiente, mas o monte de Fibonacci não é. Fila de Brodal está provado que é maximamente eficiente teoricamente, mas é difícil de implementar e na prática muito mais lenta que outras implementações de filas prioritárias.
Você também pode implementar uma fila de prioridade com um Skip list. Minha experiência é que uma fila de prioridade de lista de pulos é tão rápida quanto, e às vezes muito mais rápida que, uma pilha binária.
Existem muitas implementações diferentes da estrutura de dados da fila de prioridade. Você pode encontrar uma lista parcial em https://en.wikipedia.org/wiki/Heap_(data_structure)#Variants.