2009-11-24 2 views
0

Dans une implémentation en tas de la file d'attente de priorité ADT, l'élément ayant la valeur de priorité la plus élevée est toujours à l'avant ou à la racine du tableau?Implémentations en tas

Ou est-ce, où est la file d'attente de priorité ADT qui a la valeur de priorité la plus élevée dans l'emplacement n-1 de la matrice?

Répondre

1

La façon dont les files d'attente prioritaires sont implémentées, la valeur la plus prioritaire est toujours à la première (zéro) position du tableau. Ils sont généralement mis en œuvre comme un tas:

index 0 1 2 3 4 5 6 7 8 9 
parent/0 0 1 1 2 2 3 3 4 

Ceci est parce que le parent se trouve facilement par

(index - 1)/2 

(lors de l'utilisation division entière)

1

Vous pouvez annuler la priorité et obtenir ce que vous voulez .

Mais ce n'est pas à dire correctement sur le slot n-1 car il s'agit d'un détail d'implémentation (dans ce cas en C++) si vous voulez dire le template de classe std::priority_queue. Et ce n'est déjà pas sur ADT mais les détails de mise en œuvre. Vous pouvez réellement l'utiliser pour votre but: E.g. la file d'attente prioritaire habituelle pour int est std::priority_queue<int>, mais avec des priorités opposées est std::priority_queue<int, std::vector<int>, std::greater<int> >