改进优先队列堆中的关键搜索时间复杂度

Question

我有一个自定义任务 class，其中包含一个优先级值以及一些附加字段，如下所示：

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 值的 Task 对象，由于线性搜索（使用基本的 Tasks 数组作为堆），必须在 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;
}

我遇到了一些对 "modified heap" 的引用，可以用来将 ID 搜索改进到 O(1) 时间，但还没有找到具体的实现示例。这可能吗？如果可以，我该怎么做？非常感谢 Java 或伪代码示例，但即使只是开始搜索的相关数据结构的名称也会有所帮助。感谢您的帮助。

编辑：按要求添加的附加代码：

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

你可以做的是添加一个 HashMap 来映射最大堆中的 ID 和 Task 对象。

然后在添加或删除项目时，您可以在 HashMap<String, Task> 中添加或删除它。这些操作将花费 O(1)，因此不会损害最大堆的时间复杂度。通过使用 HashMap 除了最大堆，您可以检查给定的 ID 是否存在并在 O(1).

中检索它的项目

提醒一句：如果您 return 通过这些额外的方法引用最大堆中的对象，则外部人员可以更改项目的值，从而破坏最大堆。通过 return 对象的深度克隆或让你的 Task 不可变来解决它。

添加代码后更新：

创建 HashMap<String, Task> 的 class 的新成员并在构造函数中初始化它。
在添加方法中检查给定 Task 是否为 a.containsKey()。如果不将其添加到最大堆和 HashMap.
根据需要更新其他方法的逻辑。

改进优先队列堆中的关键搜索时间复杂度

Improving Key Search Time Complexity in a Priority Queue Heap

java

algorithm

priority-queue

data-structures

max-heap