File d'attente prioritaire avec priorités d'éléments dynamiques

Question

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.

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?

Answer 1

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); 
    } 
} 

Answer 2

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».

Answer 3

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.

Answer 4

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.

Answer 5

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é.