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

Question

我有一个优先级队列最大堆，其中每个元素都是一个 class 称为任务，如下所示（在 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

A 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 and remove API 方法来实现您需要的操作，同时确保优先级队列设计的时间复杂度 (O(log n))。

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

Time Complexity of Differentiating Priority Queue Heap Via Key

java

heap

binary-tree

scheduling

priority-queue