2

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

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;
}

我遇到了几个对“修改堆”的引用，可用于将 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.
4

1 回答 1

3

您可以做的是在最大堆中的对象和对象HashMap之间添加一个映射。IDTask

然后，在添加或删除项目时，您可以从HashMap<String, Task>. 这些操作将O(1)不会损害 Max Heap 的时间复杂度。通过使用HashMap除了 Max Heap 之外，您可以检查给定是否ID存在并在O(1).

提醒一句：如果您通过这些额外的方法返回对 Max Heap 中对象的引用，则外人可以更改项目的值并因此破坏 Max Heap。通过返回对象的深层克隆或让您的Task不可变来解决它。

添加代码后更新：

  • 创建类的新成员HashMap<String, Task>并在构造函数中对其进行初始化。
  • 在 add 方法中检查a.containsKey()给定的Task. 如果不将其添加到 Max Heap 和HashMap.
  • 根据需要更新其他方法的逻辑。
于 2017-07-04T17:31:32.680 回答