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;
}
}
它们按优先级存储在最大堆中,这很好。但是,如果我想找到具有特定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示例将不胜感激,但即使只是开始搜索的相关数据结构的名称也会很有帮助。谢谢你的帮助。
private Task[] heap;
private int heapSize, capacity;
int maxTasksHigh;
public PQ(int maxTasks){
this.capacity = maxTasks+1;
heap = new Task[this.capacity];
heapSize = 0;
maxTasksHigh = maxTasks;
}
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);
}