2010-02-18 6 views
14

J'ai besoin d'implémenter une file d'attente prioritaire où la priorité d'un élément dans la file d'attente peut changer et la file d'attente s'ajuste afin que les éléments soient toujours supprimés dans le bon ordre. J'ai quelques idées de comment je pourrais implémenter ceci mais je suis sûr que c'est une structure de données assez commune ainsi j'espère pouvoir utiliser une implémentation par quelqu'un de plus intelligent que moi comme base.File d'attente prioritaire avec priorités d'éléments dynamiques

Quelqu'un peut-il me dire le nom de ce type de file d'attente de priorité afin que je sache quoi chercher ou, mieux encore, me diriger vers une implémentation?

+0

Voir http://stackoverflow.com/questions/927631/-there-a-heap-class-in-c-that-supports-changing-the-priority-of-elements-othe et http: // stackoverflow.com/questions/450180/a-priority-queue-which-allows-efficient-priority-update –

Répondre

2

Je suggère d'abord essayer la tête dans l'approche, de mettre à jour une priorité:

  • supprimer l'élément de la file d'attente
  • revissez avec la nouvelle priorité

En C++, cela peut être fait en utilisant un std::multi_map, l'important est que l'objet doit se souvenir où il est stocké dans la structure pour pouvoir se supprimer efficacement. Pour réinsérer, c'est difficile puisque vous ne pouvez pas présumer que vous savez quelque chose sur les priorités.

class Item; 

typedef std::multi_map<int, Item*> priority_queue; 

class Item 
{ 
public: 
    void add(priority_queue& queue); 
    void remove(); 

    int getPriority() const; 
    void setPriority(int priority); 

    std::string& accessData(); 
    const std::string& getData() const; 

private: 
    int mPriority; 
    std::string mData; 

    priority_queue* mQueue; 
    priority_queue::iterator mIterator; 
}; 

void Item::add(priority_queue& queue) 
{ 
    mQueue = &queue; 
    mIterator = queue.insert(std::make_pair(mPriority,this)); 
} 

void Item::remove() 
{ 
    mQueue.erase(mIterator); 
    mQueue = 0; 
    mIterator = priority_queue::iterator(); 
} 

void Item::setPriority(int priority) 
{ 
    mPriority = priority; 
    if (mQueue) 
    { 
    priority_queue& queue = *mQueue; 
    this->remove(); 
    this->add(queue); 
    } 
} 
+0

Merci Matthieu, j'ai pensé à en utilisant cette approche, mais en raison de la fréquence de mise à jour, il n'était pas assez efficace pour mes besoins. J'ai fini par utiliser une implémentation qui incluait des éléments de mappage de dictionnaire vers leurs index dans la file d'attente, puis une méthode dans la file d'attente, UpdatePosition (Item item), qui recherche l'index des éléments et le place dans sa nouvelle position. La file d'attente a ensuite un événement auquel les éléments s'inscrivent afin qu'ils notifient la file d'attente lorsque leurs priorités changent. Cela semble bien fonctionner. – sean

0

Google has a number of answers pour vous, y compris une implémentation de one in Java. Cependant, cela ressemble à quelque chose qui serait un problème de devoirs, donc si c'est le cas, je suggérerais d'essayer d'abord les idées vous-même, puis potentiellement référencer l'implémentation de quelqu'un d'autre si vous êtes coincé quelque part et avez besoin d'un pointeur dans la bonne direction. De cette façon, vous êtes moins susceptible d'être «biaisé» par rapport à la méthode de codage précise utilisée par l'autre programmeur et plus susceptible de comprendre pourquoi chaque élément de code est inclus et comment cela fonctionne. Parfois, il peut être un peu trop tentant de faire l'équivalent paraphrasant de «copier-coller».

+1

Merci Dav mais c'est une file d'attente prioritaire standard. Si j'ajoute un élément à la file d'attente et que sa priorité est modifiée (en dehors de la file d'attente), l'ordre de la file d'attente peut être incorrect. En d'autres termes, une file d'attente de priorité standard ne fait que trier les éléments lorsqu'ils sont ajoutés à la file d'attente et non plus tard. J'ai besoin d'implémenter une file d'attente qui se met à jour en tant que priorité de ses éléments mises à jour. P.S. Ce n'est pas un problème de devoirs, j'ai besoin de le mettre en œuvre dans le cadre de certains logiciels de simulation. J'ai quelques idées de comment je peux l'implémenter mais je veux voir s'il y a une meilleure façon de le faire. – sean

+0

Ah. D'accord. Dans ce cas, je suggérerais de rechercher des exemples d'implémentations de l'algorithme de Dijkstra, qui (s'il est implémenté dans sa forme la plus efficace) nécessite une file d'attente prioritaire réorganisable, et devrait donc probablement avoir ce que vous cherchez. – Amber

5

Un tas binaire standard prend en charge les opérations 5 (l'exemple ci-dessous présupposent un tas max):

* find-max: return the maximum node of the heap 
* delete-max: removing the root node of the heap 
* increase-key: updating a key within the heap 
* insert: adding a new key to the heap 
* merge: joining two heaps to form a valid new heap containing all the elements of both. 

Comme vous pouvez le voir, dans un tas max, vous pouvez augmenter une clé arbitraire. Dans un tas min, vous pouvez réduire une clé arbitraire. Vous ne pouvez malheureusement pas changer les clés dans les deux sens, mais cela va-t-il se faire? Si vous avez besoin de changer les clés dans les deux sens, vous voudrez peut-être penser à utiliser un min-max-heap.

+0

Je ne vois pas comment un tas binaire pourrait supporter efficacement l'incrément si vous devez d'abord rechercher l'élément que vous souhaitez augmenter. Comme il n'y a pas d'ordre dans le tas, il faudra un temps linéaire pour trouver l'élément. – wcochran

+2

Vous devez avoir une référence à l'élément afin de rendre efficace l'incrémentation et la réduction. Ceci est implémenté avec des handles dans la bibliothèque Boost.Heap C++ http://www.boost.org/doc/libs/1_55_0/doc/html/heap/concepts.html#heap.concepts.mutability – lazd

0

Je cherche exactement la même chose!

Et voici une partie de mon idée:

  1. Depuis une priorité d'un élément ne cesse de changer, il n'a pas de sens pour trier la file d'attente avant de récupérer un élément. Donc, nous devrions oublier d'utiliser une file d'attente prioritaire. Et "partiellement" trier le conteneur lors de la récupération d'un élément.

Et choisissez parmi les algorithmes de tri STL suivants: a. partition b. stable_partition c. nth_element d. partial_sort e. partial_sort_copy f. trier g.stable_sort

partition, stable_partition et nth_element sont des algorithmes de tri linéaires, ce qui devrait être notre premier choix. MAIS, il semble qu'il n'y ait pas ces algorithmes fournis dans la bibliothèque Java officielle. Par conséquent, je vais vous suggérer d'utiliser java.util.Collections.max/min pour faire ce que vous voulez.

7

Les files d'attente prioritaires telles que celle-ci sont généralement implémentées en utilisant une structure de données de tas binaire telle que suggérée par quelqu'un d'autre, qui est généralement représentée par un tableau mais peut également utiliser une arborescence binaire. Il n'est en fait pas difficile d'augmenter ou de diminuer la priorité d'un élément dans le tas. Si vous savez que vous modifiez la priorité de nombreux éléments avant que l'élément suivant n'apparaisse dans la file d'attente, vous pouvez désactiver temporairement le réordonnancement dynamique, insérer tous les éléments à la fin du segment, puis réorganiser le tas entier (à un coût de O (n)) juste avant que l'élément ait besoin d'être sauté. La chose importante à propos des tas est que ça coûte seulement O (n) de mettre un tableau dans l'ordre du tas mais O (n log n) pour le trier.

J'ai utilisé cette approche avec succès dans un grand projet avec des priorités dynamiques.

Voici ma mise en œuvre d'un priority queue implementation in the Curl programming language paramétré.

Questions connexes