java - 提高优先级队列堆中的关键字搜索时间复杂度

我有一个自定义任务类，它包含一个优先级值和一些附加字段，如下所示：

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
}

它们按优先级存储在最大堆中，这很好。但是，如果要查找具有特定ID值的任务对象，则由于线性搜索（使用基本任务数组作为堆），必须在O（n）时间内完成：

public int getTimeOfID(int ID){

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

    return -1;
}

我遇到了一些对“修改堆”的引用，可以用来将ID搜索提高到O（1）次，但还没有找到具体的实现示例这有可能吗？如果有，我该怎么做一个Java或pseudcode示例将非常受欢迎，但即使只是一个相关数据结构的名称来开始我的搜索也会很有帮助谢谢你的帮助。
编辑：根据要求添加的附加代码：

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

最佳答案

您可以添加一个HashMap来映射max堆中的ID和Task对象。
然后在添加或删除项目时，您可以在HashMap<String, Task>中添加或删除该项目这些操作将采用O(1)，这样不会损害最大堆的时间复杂度。通过使用除最大堆外，您可以检查给定的HashMap是否存在，并在ID中检索其项。
注意：如果您通过这些额外的方法返回对Max堆中对象的引用，外部人员可以更改项的值，从而破坏Max堆通过返回对象的深层克隆或使O(1)不可变来解决此问题。
添加代码后更新：
创建Task类的新成员并
在构造函数中初始化它。
在add方法中，检查给定的HashMap<String, Task>是否a.containsKey()。如果没有，则将其添加到最大堆和Task。
根据需要更新其他方法的逻辑。