改进优先级队列堆中的密钥搜索时间复杂性

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.