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

的复杂性我有个优先级队列的最大堆，每个元素都是一个叫任务类，如下所示（在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）中完成，我根本不理解。任何人都可以澄清我接近这个错误的地方吗？

来源

2017-07-02 Chase

您选择的标签没有太多追随者，我建议您使用语言标签，即使这个问题是与语言无关的 –

好的提示，谢谢。 – Chase

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)）。

来源

2017-07-02 02:38:41

我应该澄清，我没有使用PriorityQueue，我将堆存储在一个数组中。但是你的回答给了我一个想法，即我可以为Insert添加一个额外的条件，如果Priorities是相同的，那么将较低的ID放在堆上。然后我上面描述的操作每次只需要对根进行操作。不是一个直接的答案，但你让我思考着正确的方向，所以谢谢！ – Chase

从我不使用PriorityQueue实用程序的意义上说，我从头创建了实现。我知道PriorityQueue也使用了一个数组，这可能会更好。 – Chase

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

回答

相关问题