Por que a maioria dos idiomas fornece uma implementação de min-heap em vez de uma max-heap?

19

Acabei de perceber algo e me pergunto se existe alguma razão para isso. Exceto pelo C ++ (std :: priority_queue é um heap máximo), não conheço nenhuma outra linguagem que ofereça um heap máximo.

O módulo heapq do Python implementa um min-heap binário no topo de uma lista.

A biblioteca de Java contém uma classe PriorityQueue, que implementa uma fila de prioridade mínima.

A biblioteca do Go contém um módulo container / heap, que implementa um min-heap sobre qualquer estrutura de dados compatível.

A estrutura Core Foundation da Apple contém uma estrutura CFBinaryHeap, que implementa uma min-heap.

Acho um max-heap mais intuitivo que um min-heap e acredito que tecnicamente a diferença de implementação é apenas uma questão de alterar um operador de comparação. Existe algum motivo real? A maioria dos aplicativos precisa de um min em vez de um heap máximo? desde já, obrigado

design algorithms Bernardo Pires
fonte
Eles não são exatamente a mesma coisa? Eu voto para fechar como argumentativo.
2
Apenas alguns dias atrás, eu precisava de um heap mínimo em C ++ e fiquei um pouco irritado porque o priority_queue assumiu como padrão o heap máximo. Isso me forçou a definir o operador> na minha classe personalizada, que já tinha o operador <. Ao trabalhar com gráficos, você geralmente deseja priorizar as arestas mais curtas, portanto, precisa de um mínimo de heap.
LaC
2
@LaC: você pode usar std::not2(std::less<T>()).

Respostas:

9

Como outros observaram, se o heap aceita um comparador, não é muito difícil obter um comportamento ou outro. Uma rápida leitura do Google Code, no entanto, sugere que o min-heap é muito mais prevalente no código real, devido a dois aplicativos que surgem repetidamente.

  • Dijkstra / A * / muitos outros algoritmos de caminho mais curto (porque os caminhos parciais ficam mais longos).

  • Simulação de eventos (porque o tempo avança).

Além disso, eu argumentaria que, como a classificação padrão retorna itens pequenos a grandes, o mesmo deve acontecer com a pilha padrão.

slowpoke
fonte
2
Normalmente programa em C ++ e me pergunto o contrário: por que o C ++ não implementa um min-heap? Como você disse, a maioria dos algoritmos usa um min-heap.
Martín Fixman 17/05
5

É apenas uma questão de gosto. Eu não acho que haverá qualquer razão específica. É como algumas pessoas gostam de expressar problemas de otimização como custos minimizados, enquanto outros gostam de maximizar lucros.


fonte
3

A maioria dos idiomas que conheço permite passar um parâmetro para decidir se deve ser um heap mínimo ou máximo. Portanto, o valor padrão é um pouco arbitrário. Eu acho que, para a maioria dos idiomas, é uma questão de consistência definir qual é o operador padrão. Para C ++ no stl, o padrão está std::lesslevando a um min-heap.

A consistência de usar std::lesscomo padrão em qualquer lugar significa que você só precisa implementar essa comparação quando estiver usando qualquer tipo de estrutura de dados e não precisar decidir em qual estrutura de dados usará mais tarde ao criar suas classes. Eu acho que é o mesmo para outras línguas, com a única diferença de que uma comparação maior que o padrão.

LiKao
fonte
3
Eu não acho que exista essa conexão. Você pode implementar qualquer tipo de heap usando <ou>. De fato, std :: less é o padrão no STL, mas eles implementam um heap máximo em vez de um heap mínimo.
LaC
1

Basicamente, o valor do índice é um número arbitrário. Se você acredita que o número representa uma prioridade e números maiores são prioridades mais altas, um heap máximo faz sentido. Mas se os números representam, por exemplo, números conceituais de padaria ("Pegue um número"), então min-heap faz mais sentido.

Você sempre pode converter de um para o outro usando o complemento 1 do índice.

Daniel R Hicks
fonte