时间区分优先级队列堆通过重点

Question

的复杂性我有个优先级队列的最大堆，每个元素都是一个叫任务类，如下所示（在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时从堆中删除它。但是，这里有一个问题：允许多个Task同样优先。在这种情况下，我比较所有这些任务的ID分数，并在最低的一个上进行操作。

这样的操作最糟糕的运行时间是多少？如果每个元素具有相同的优先级，我最终将搜索整个树，这意味着这不可能在小于O（n）的时间内完成，对吗？这似乎不可能解决，因为ID是未分类的。然而，我被告知这可能在O（log n）中完成，我根本不理解。任何人都可以澄清我接近这个错误的地方吗？

Answer 1

java.util.PriorityQueue A（的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)）。