Diferença entre um heap e uma fila de prioridade

36

Eu sempre pensei que pilhas e filas de prioridade foram sinônimos - uma estrutura de dados abstrata que suporta os insert, findMine deleteMinoperações.

Alguma literatura parece concordar comigo - Estruturas de Dados Puramente Funcionais de Chris Okasaki (capítulo 3), por exemplo.

Por outro lado, a página de heap da Wikipedia a define como uma estrutura de dados baseada em árvore e afirma que os heaps são uma implementação concreta de filas prioritárias.

Estou tendo uma grande dificuldade em conciliar isso com o fato de que posso pensar em mais de uma implementação de heap - pilhas esquerdistas, pilhas binomiais, pilhas espalhadas ...

O simples fato de um heap poder ser implementado com diferentes estruturas de dados não significa, por definição, que é uma estrutura de dados abstrata? E se for esse o caso, existe uma diferença real nas filas de prioridades?

data-structures Nicolas Rinaudo
fonte
11
Leia a página da Wikipedia sobre filas prioritárias ( en.wikipedia.org/wiki/Priority_queue ), que diz que "uma fila prioritária pode ser implementada com uma pilha ou uma variedade de outros métodos, como uma matriz não ordenada" - e essa é realmente a resposta para sua pergunta.
Doc Brown
2
Bem, na verdade não - isso não me ajuda a entender se um heap é uma estrutura de dados concreta ou abstrata. Eu diria que é abstrato, já que existem muitas implementações concretas de um monte. Se esse for o caso, e uma lista de prioridades e um heap são estruturas de dados abstratas com as mesmas propriedades, preciso de ajuda para entender a diferença e dizer que uma é uma possível implementação da outra não é muito útil, se nenhuma delas é realmente uma implementação concreta.
Nicolas Rinaudo
As coisas são ainda piores: uma pilha binária pode ser implementada como uma matriz ou como uma árvore binária. Felizmente, ainda não ouvi falar de uma matriz implementada como outra coisa.
Alexey19

Respostas:

25

Uma fila de prioridade pode ter qualquer implementação, como uma matriz que você pesquisa linearmente quando você pop. Tudo o que isso significa é que, quando você abre, obtém o valor com o mínimo ou o máximo dependendo.

Um heap clássico como normalmente é referido é geralmente um heap mínimo. Uma implementação que possui boa complexidade de tempo ( O(log n)push e pop) e sem sobrecarga de memória.

catraca arrepiante
fonte
4
Você quer dizer que a diferença é que, enquanto eles compartilham as mesmas operações ( findMin, deleteMin, insert), montes têm garantidas "boas" complexidades para eles, onde filas de prioridade não?
Nicolas Rinaudo 31/08
O heap também não pode ter implementações diferentes com complexidades de tempo diferentes (uma árvore binária vinculada usual, por exemplo)? Além disso, a complexidade do tempo depende da memória usada. Se for uma fita magnética, não haverá O(log(n))empurrão e pop, suponho.
21418 Alexey
6

Este site fornece uma explicação muito clara. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Em resumo, uma fila de prioridade pode ser implementada usando muitas das estruturas de dados que já estudamos (uma matriz, uma lista vinculada ou uma árvore de pesquisa binária). No entanto, essas estruturas de dados não fornecem as operações mais eficientes. Para tornar todas as operações muito eficientes, usaremos uma nova estrutura de dados chamada heap.

Chihung Yu
fonte
11
Observe que, no resumo da página à qual você vinculou, a própria fila de prioridade é chamada de estrutura de dados .
Alexey
2

Eu acho que o que você escreveu sobre concreto vs abstrato está correto. Porém, onde você diz que pilhas de pilhas, pilhas de binômios são implementações diferentes de pilhas, acho que é mais correto dizer que são tipos diferentes de pilhas. Heap, penso que é uma categoria de implementação que geralmente garante não apenas a mesma interface, mas também os mesmos tempos de acesso.

Você vê isso com mapas associativos e tabelas de hash e árvores de pesquisa binária também. Bsts e tabelas de hash são estruturas de dados concretas que fornecem a interface abstrata do mapa associativo. Árvores negras vermelhas e árvores avl são ambas balsas equilibradas, com as mesmas grandes garantias de O e a mesma interface adicional (em ordem de travessia). São tipos diferentes de árvores, eu diria mais do que diferentes implementações de árvores. São implementações diferentes, mas intimamente relacionadas, de mapas associativos.

Nir Friedman
fonte