Différence entre un tas et une file d'attente prioritaire

36

J'ai toujours pensé que les tas et les files d'attente prioritaires étaient des synonymes - une structure de données abstraite qui prend en charge les opérations insert, findMinet deleteMin.

Certains auteurs semblent être d’accord avec moi, par exemple les structures de données purement fonctionnelles de Chris Okasaki (chapitre 3).

D'autre part, la page de tas de Wikipédia la définit comme une structure de données basée sur une arborescence et indique que les tas sont une implémentation concrète de files d'attente prioritaires.

J'ai du mal à concilier cela avec le fait que je peux penser à plus d'une mise en œuvre de tas: tas de gauche, tas de binômes, tas de disques ...

Le simple fait qu’un tas puisse être implémenté avec différentes structures de données ne signifie-t-il pas, par définition, qu’il s’agit d’une structure de données abstraite? Et si tel est le cas, existe-t-il une différence réelle avec les files d'attente prioritaires?

data-structures Nicolas Rinaudo
la source
11
Lisez la page Wikipedia sur les files d’attente prioritaires ( en.wikipedia.org/wiki/Priority_queue ), il est écrit: "une file d’attente prioritaire peut être implémentée avec un tas ou une variété d’autres méthodes, comme un tableau non ordonné" - et c’est la réponse à ta question.
Doc Brown
2
Eh bien, pas vraiment - cela ne m'aide pas à comprendre si un tas est une structure de données concrète ou abstraite. J'aurais tendance à en dire un abstrait, car il existe de nombreuses implémentations concrètes d'un tas. Si tel est le cas, et si une liste de priorités et un segment de mémoire sont des structures de données abstraites ayant les mêmes propriétés, il me faut une aide pour comprendre la différence. mise en œuvre concrète.
Nicolas Rinaudo
La situation est encore pire: un segment de mémoire binaire peut être implémenté sous forme de tableau ou d'arborescence. Heureusement, je n'ai pas encore entendu parler d'un tableau implémenté comme autre chose.
Alexey

Réponses:

25

Une file d'attente prioritaire peut avoir n'importe quelle implémentation, comme un tableau dans lequel vous effectuez une recherche linéaire lorsque vous ouvrez une fenêtre. Tout ce que cela signifie, c'est que lorsque vous ouvrez une fenêtre, vous obtenez la valeur avec le minimum ou le maximum en fonction.

Un segment classique, auquel il est généralement fait référence, est généralement un segment minimal. Une implémentation qui a une bonne complexité temporelle ( O(log n)sur push et pop) et aucune surcharge de mémoire.

monstre à cliquet
la source
4
Voulez - vous dire dire que la différence est que si elles partagent les mêmes opérations ( findMin, deleteMin, insert), ont des tas garantis « bonnes » complexités pour eux où les files d' attente prioritaires ne le font pas?
Nicolas Rinaudo
Le tas ne peut-il pas aussi avoir différentes implémentations avec différentes complexités temporelles (un arbre binaire lié habituel, par exemple)? En outre, la complexité temporelle dépend de la mémoire utilisée. Si c'est une bande magnétique O(log(n)), je suppose qu'il n'y aura pas de push and pop.
Alexey
6

Ce site fournit une explication très claire. http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

En bref, une file d'attente prioritaire peut être mise en œuvre en utilisant la plupart des structures de données que nous avons déjà étudiées (un tableau, une liste chaînée ou un arbre de recherche binaire). Cependant, ces structures de données ne fournissent pas les opérations les plus efficaces. Pour rendre toutes les opérations très efficaces, nous utiliserons une nouvelle structure de données appelée tas.

Chihung Yu
la source
1
Notez que dans le résumé de la page à laquelle vous êtes lié, la file d’attente prioritaire elle-même est appelée structure de données .
Alexey
2

Je pense que ce que vous avez écrit sur Concrete vs Abstract est correct. Lorsque vous dites que les tas évasés, les tas binomiaux sont des implémentations différentes des tas, je pense qu’il est plus correct de dire que ce sont des types de tas différents. Je pense que Heap est une catégorie d'implémentation qui garantit généralement non seulement la même interface, mais également les mêmes temps d'accès.

Vous le voyez également avec les cartes associatives, les tables de hachage et les arbres de recherche binaires. Les tables Bsts et hash sont des structures de données concrètes qui fournissent l'interface abstraite de carte associative. Les arbres noirs et rouges et les arbres avl sont tous deux des bsts équilibrés, avec les mêmes grandes garanties O et la même interface supplémentaire (par ordre de parcours). Ce sont différents types d'arbres, je dirais plus que différentes implémentations d'arbres. Ce sont des implémentations différentes mais étroitement liées des cartes associatives.

Nir Friedman
la source