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

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
}

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

此类操作最坏情况下的运行时间是多少？如果每个元素都有相同的优先级，我最终会搜索整个树，这意味着这不可能在少于 O(n) 的时间内完成，对吗？这似乎无法解决，因为 ID 未排序。然而，我被告知这可以在 O(log n) 中完成，我根本不明白。有人能澄清我在哪里处理这个错误吗？

Answer 1

java.util.PriorityQueue(Task 实例)constructor可以采用一个Comparator来考虑Task#Priority和Task#ID，这意味着(优先级)联系可以基于关于 ID(据说)是唯一的。因此，任务 t1(Priority=5, ID=100, Time=10) 可以先于(即优先于)任务 t2(Priority=5, ID=110, Time= 10)。

删除这样一个具有最高优先级的项目(位于根)以及其他可能具有相同优先级的项目，剩余时间为零和最低 ID 仍然是 O(log (n)) 在堆或优先级队列中进行操作，同时维护堆属性。请注意，优先级队列不太适合搜索(哈希表或二叉搜索树就可以很好地做到这一点)；但用于在维护堆属性的同时插入或删除。您应该只使用peek和 remove API 方法可实现您所需的操作，同时确保优先级队列设计的时间复杂度 (O(log n))。