structure de données de la file d'attente prioritaire

Question

Supposons que j'ai une file d'attente prioritaire qui supprime les éléments dans l'ordre croissant, et stockés dans cette file d'attente sont les éléments 1, 1, 3, 0, 1. L'ordre croissant est 0 puis 1 puis 3, mais il y a trois éléments 1 s.

Quand j'appelle remove il va d'abord enlever le 0, mais si je l'appelle remove à nouveau se il supprimer tous les trois 1 s en même temps, ou aurai-je besoin d'appeler remove à trois reprises pour enlever tous les 1 éléments .

Un appel à remove sur une telle file d'attente prioritaire supprime-t-il tous les éléments de la même valeur minimale ou un seul élément sera-t-il supprimé à chaque appel?

Answer 1

Dans une file d'attente prioritaire, l'opération de suppression supprime généralement un seul enregistrement contenant la valeur maximale. Donc, dans votre cas, ce serait la deuxième option. L'ordre de suppression n'est pas garanti. Toute clé avec la valeur "maximum" serait supprimée. De plus, le tableau non trié est une mauvaise structure de données qui implémente une file d'attente prioritaire. Vous utiliserez généralement une structure de données en tas pour obtenir des garanties O (log (n)) lors de l'insertion et de la suppression.

Answer 2

mise en œuvre du tas typique serait toujours reheap l'arbre donc supprimerait 0, 1, 1, 1 et 3 en 1 obtiendrait pousser à la racine pendant reheapification ..

que je me trompe?

modifier: votre cas est un min-tas