Pourquoi la plupart des langues fournissent-elles un min-tas au lieu d'une implémentation de max-tas?

19

Je viens de remarquer quelque chose et je me demande s'il y a une raison à cela. À l'exception de C ++ (std :: priority_queue est un tas max), je ne connais aucun autre langage qui offre un tas max.

Le module heapq de Python implémente un min-tas binaire en haut d'une liste.

La bibliothèque de Java contient une classe PriorityQueue, qui implémente une file d'attente à priorité min.

La bibliothèque de Go contient un module conteneur / tas, qui implémente un min-tas au-dessus de toute structure de données compatible.

Le framework Core Foundation d'Apple contient une structure CFBinaryHeap, qui implémente un min-heap.

Je trouve un max-tas plus intuitif qu'un min-tas et je crois que techniquement la différence d'implémentation n'est qu'une question de changer d'opérateur de comparaison. Y a-t-il une vraie raison? La plupart des applications ont besoin d'un segment min au lieu d'un segment max? Merci d'avance

design algorithms Bernardo Pires
la source
N'est-ce pas exactement la même chose? Je vote pour terminer comme argumentatif.
2
Il y a quelques jours à peine, j'avais besoin d'un segment minimum en C ++ et j'étais un peu ennuyé que la priorité de la file d'attente par défaut soit un segment maximum. Cela m'a obligé à définir l'opérateur> sur ma classe personnalisée, qui avait déjà l'opérateur <. Lorsque vous travaillez avec des graphiques, vous souhaitez généralement hiérarchiser les bords les plus courts, vous avez donc besoin d'un segment minimum.
LaC
2
@LaC: vous pouvez utiliser std::not2(std::less<T>()).

Réponses:

9

Comme d'autres l'ont observé, si le tas accepte un comparateur, il n'est pas trop difficile d'obtenir un comportement ou l'autre. Une lecture rapide de Google Code, cependant, suggère que min-heap est de loin plus répandu dans le code réel, en raison de deux applications qui reviennent encore et encore.

  • Dijkstra / A * / de nombreux autres algorithmes de chemin le plus court (car les chemins partiels s'allongent).

  • Simulation d'événement (car le temps passe).

En outre, je dirais que, comme le tri par défaut renvoie des éléments petits à grands, le tas par défaut devrait en faire de même.

lambin
la source
2
Je programme habituellement en C ++, et je me demande le contraire: pourquoi C ++ n'implémente-t-il pas un min-heap? Comme vous l'avez dit, la plupart des algorithmes utilisent un min-tas.
Martín Fixman
5

C'est juste une question de goût. Je ne pense pas qu'il y aura de raison spécifique. C'est tout comme certaines personnes aiment exprimer les problèmes d'optimisation en minimisant les coûts, tandis que d'autres préfèrent maximiser les bénéfices.


la source
3

La plupart des langues que je connais permettent de passer un paramètre pour décider s'il doit s'agir d'un tas min ou max. La valeur par défaut est donc quelque peu arbitraire. Je suppose que pour la plupart des langues, c'est une question de cohérence de définir ce qu'est l'opérateur par défaut. Pour C ++ dans la stl, la valeur par défaut std::lessconduit à un tas min.

La cohérence de l'utilisation std::lesspar défaut partout signifie que vous n'avez à implémenter cette comparaison que lorsque vous utilisez n'importe quel type de structure de données et vous n'avez pas à décider quelle structure de données vous allez utiliser plus tard lorsque vous concevez vos classes. Je suppose que c'est la même chose pour les autres langues, à la seule différence qu'une comparaison supérieure à est la norme.

LiKao
la source
3
Je ne pense pas qu'il existe un tel lien. Vous pouvez implémenter l'un ou l'autre type de tas en utilisant <ou>. En effet, std :: less est la valeur par défaut dans STL, mais ils implémentent un tas max au lieu d'un tas min.
LaC
1

Fondamentalement, la valeur d'index est un nombre arbitraire. Si vous pensez que le nombre représente une priorité et que des nombres plus importants sont des priorités plus élevées, alors un tas max a du sens. Mais si les nombres représentent, par exemple, des nombres conceptuels de boulangerie ("Take a number"), alors min-tas a plus de sens.

Vous pouvez toujours convertir de l'un à l'autre en prenant le complément 1 de l'indice.

Daniel R Hicks
la source