通过键区分优先级队列堆的时间复杂度

Question

我有一个优先级队列最大堆，其中每个元素都是一个名为Task的类，如下所示（在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
}

堆显然是按优先级排序的。我要执行的操作是查找优先级最高的项目，递减其 Time 值，并在时间分数更改为 0 时将其从堆中删除。但是，这里有一个问题：允许有多个具有相同优先级的任务。在这种情况下，我比较所有此类任务的ID分数，并对最低的任务进行操作。

此类操作的最坏运行时间是多少？如果每个元素都有相同的优先级，我最终会搜索整个树，这意味着这不可能在少于O（n）的时间内完成，对吗？这似乎是不可能的，因为ID是未排序的。但是，我被告知这可以在O（log n）中完成，我完全不明白。有谁能澄清我在哪里错了？

Answer 1

Java.util.PriorityQueue（任务实例）构造函数可以采用一个比较器，该比较器可以考虑任务#优先级和任务#ID，这意味着（优先级）关系可以根据ID（假定）唯一的ID被破坏。因此，任务 t1（优先级 = 5，ID = 100，时间 = 10）可以位于（即优先于）任务 t2（优先级 = 5，ID = 110，时间 = 10）之前。

删除具有最高优先级的项（位于根）以及其他具有相同优先级、零剩余时间和最低ID的项仍然是堆或优先级队列中的＜code＞O（log（n））