Complexité de Différencier Priorité Queue Heap Via Key

Question

J'ai un tas file d'attente prioritaire max où chaque élément est une classe appelée tâche, qui se présente comme suit (implémenté en Java, mais la question est la langue agnostique):

class Task{ 

    int ID 
    int Priority 
    int Time 

    public Task(int i, int p, int t){ 
     this.ID = i; 
     this.Priority = p; 
     this.Time = t; 
    } 

    //Getters, etc 
} 

Le tas est évidemment trié par priorité. L'opération que je souhaite effectuer consiste à trouver l'élément de priorité la plus élevée, à diminuer sa valeur Time et à la retirer du tas si le score de temps passe à 0. TOUTEFOIS, voici la capture: il est possible d'avoir plusieurs tâches avec même priorité. Dans ce cas, je compare les scores ID de toutes ces Tâches et opère sur le plus bas.

Quel serait le pire temps de fonctionnement d'une telle opération? Si chaque élément a la même priorité, je finirais par chercher dans tout l'arbre, ce qui signifie que cela ne pourrait pas être fait en moins de O (n) temps, correct? Cela semble impossible à contourner parce que les identifiants ne sont pas triés. Cependant, on me dit que c'est possible de faire en O (log n), ce que je ne comprends pas du tout. Quelqu'un pourrait-il préciser où j'aborde ce problème?

Answer 1

A java.util.PriorityQueue (de Task cas) constructor peut prendre un Comparator qui peut prendre en compte la Task#Priority et Task#ID ce qui signifie que les (prioritaires) des liens pourraient être brisés sur la base d'ID qui sont (soi-disant) unique. Ainsi, une tâche t1(Priority=5, ID=100, Time=10) peut précéder (c'est-à-dire être prioritaire) une tâche t2(Priority=5, ID=110, Time=10).

Retrait tel un élément (qui est à la base) qui a la plus haute priorité ainsi que d'autres qui peuvent avoir la même priorité, Temps zéro restant et le plus bas ID est toujours une opération O(log(n)) en tas ou file d'attente prioritaire tout en conservant la propriété tas. Notez que les files d'attente de priorité ne sont pas bonnes pour en recherchant (les tables de hachage ou les arbres de recherche binaires le font bien); mais pour l'insertion ou la suppression tout en conservant la propriété de tas. Vous devez simplement utiliser les méthodes API peek et remove pour réaliser l'opération dont vous avez besoin tout en assurant la complexité temporelle (O(log n)) à laquelle la file d'attente prioritaire est destinée.