Verbesserung der Key Suche Zeitkomplexität in einer Prioritätswarteschlange Heap

Question

ich eine benutzerdefinierte Task-Klasse haben, die einen Prioritätswert sowie einige zusätzliche Felder enthält, wie unten gezeigt:

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 
} 

Diese in einem max Heap nach Priorität gespeichert werden das funktioniert gut. Allerdings, wenn ich will ein Task-Objekt mit einem bestimmten ID-Wert finden, die in O (n) Zeit aufgrund der linearen Suche (unter Verwendung eine grundlegende Reihe von Aufgaben als Heap) getan werden muss:

public int getTimeOfID(int ID){    

    for(int i = 1; i < heapSize+1; i++){ 
     if (heap[i].getTaskID() == taskID){ 
      return heap[i].getTimeLeft(); 
     } 
    } 

    return -1; 
} 

Ich habe mehrere Verweise auf einen "modifizierten Heap" gefunden, der verwendet werden könnte, um die ID-Suche auf O (1) -Zeit zu verbessern, aber kein konkretes Implementierungsbeispiel gefunden. Ist das möglich, und wenn ja, wie würde ich es tun? Ein Java- oder Pseudocode-Beispiel würde sehr geschätzt werden, aber auch nur der Name einer relevanten Datenstruktur, um mit meiner Suche zu beginnen, wäre hilfreich. Danke für jegliche Hilfe.

EDIT: Zusätzlicher Code hinzugefügt wie gewünscht:

//initial variables 

private Task[] heap; 
private int heapSize, capacity; 
int maxTasksHigh; 

//Constructor 

public PQ(int maxTasks){   
    this.capacity = maxTasks+1; 
    heap = new Task[this.capacity]; 
    heapSize = 0; 
    maxTasksHigh = maxTasks; 
} 

//Addition 

public void add(int ID, int time){   
    Task newTask = new Task(ID, time); 
    heapSize++; 
    heap[heapSize] = newTask; 
    int target = heapSize; 

    heap[target] = newTask; 
    reorder(target); 
} 

//etc. 

Answer 1

Was können Sie tun, ist eine HashMap hinzufügen zwischen einem ID und dem Task Objekt in der Max-Heap abzubilden.

Wenn Sie ein Element hinzufügen oder entfernen, fügen Sie es hinzu oder entfernen es aus der HashMap<String, Task>. Diese Operationen werden O(1) dauern, so dass die Zeitkomplexität des Max Heap nicht beeinträchtigt wird. Mit dem HashMap zusätzlich zu dem Max Heap können Sie überprüfen, ob eine gegebene ID existiert und seinen Artikel in O(1) abrufen.

Ein Wort der Warnung: Wenn Sie den Verweis auf das Objekt im Max Heap durch diese zusätzlichen Methoden zurückgeben, kann ein Außenstehender den Wert des Objekts ändern und daher den Max Heap unterbrechen. Lösen Sie es, indem Sie einen tiefen Klon des Objekts zurückgeben oder indem Sie Ihre Task unveränderlich lassen.

---

Update nach Code hinzufügen:

• Erstellen Sie ein neues Mitglied der Klasse von HashMap<String, Task> und initialisieren es im Konstruktor.
• In der Add-Methode überprüfen, ob a.containsKey() für die angegebenen Task. Wenn nicht, fügen Sie es dem Max Heap und dem HashMap hinzu.
• Aktualisieren Sie die Logik anderer Methoden nach Bedarf.