Zeitkomplexität von Differenziert Priority Queue Heap Via Key

Question

Ich habe eine Prioritätswarteschlange max heap, wobei jedes Element eine Klasse ist Aufgabe genannt, die wie folgt aussieht (in Java implementiert, aber Frage ist sprachunabhängig):

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 
} 

Der Heap ist offensichtlich nach Priorität sortiert. Die Operation, die ich ausführen möchte, ist das Item mit der höchsten Priorität zu finden, den Time Wert zu dekrementieren und es aus dem Heap zu entfernen, wenn sich der Time Score auf 0 ändert. JETZT ist hier der Haken: Es darf mehr als eine Task geben gleiche Priorität. In diesem Fall vergleiche ich die ID-Werte aller dieser Aufgaben und arbeite mit der niedrigsten.

Was wäre die Worst-Case-Laufzeit eines solchen Vorgangs? Wenn jedes Element dieselbe Priorität hat, würde ich am Ende den gesamten Baum durchsuchen, was bedeutet, dass dies unmöglich in weniger als 0 (n) Zeit durchgeführt werden kann, richtig? Dies scheint unmöglich zu sein, weil die IDs unsortiert sind. Allerdings wurde mir gesagt, dass dies in O (log n) möglich ist, was ich überhaupt nicht verstehe. Würde jemand klären können, wo ich mich dem Unrecht annähere?

Answer 1

A java.util.PriorityQueue (von Task Instanzen) constructor kann ein Comparator nehmen, dass die Task#Priority und Task#ID berücksichtigen kann, was bedeutet, dass die (Priorität) die Krawatten basierend auf ID gebrochen werden können, die (angeblich) einzigartig. Eine Aufgabe t1(Priority=5, ID=100, Time=10) könnte also einer Aufgabe t2(Priority=5, ID=110, Time=10) vorausgehen (d. H. Priorisiert werden). Aufrechterhaltung

einen solchen Gegenstand entfernen (die an der Wurzel ist), die zusammen mit anderen höchste Priorität hat, die die gleiche Priorität verbleibenden Zeit Null haben können und niedrigsten, während ID ist immer noch ein O(log(n)) Betrieb in einem Haufen oder priority queue die Heap-Eigenschaft Beachten Sie, dass Prioritätswarteschlangen für Suche nicht groß sind (Hash-Tabellen oder binäre Suchbäume tun das gut); aber zum Einfügen oder Entfernen, während die Heap-Eigenschaft beibehalten wird. Sie sollten nur mit den API-Methoden peek und remove arbeiten, um die erforderliche Operation zu erreichen und gleichzeitig die zeitliche Komplexität (O(log n)) zu gewährleisten, für die die Prioritätswarteschlange vorgesehen ist.