投稿

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

小星 编程 65

我有一个优先级队列最大堆，其中每个元素是一个称为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）中做到这一点，我根本不了解。谁能弄清楚我要解决这个错误的地方？

回复

共1条回复 我来回复
  • 编程小能手
    编程小能手
    来自于宇宙以外的编程小能手～
    评论

    （属于java.util.PriorityQueue实例的）Task constructor可以采用Comparator，该Task#Priority可以将Task#ID和t1(Priority=5, ID=100, Time=10)考虑在内，这意味着可以根据ID为（（应该）独特。因此，任务t2(Priority=5, ID=110, Time=10)可以位于任务O(log(n))之前（即，优先级高于）。

    除去具有最高优先级的项目（位于根目录）以及可能具有相同优先级的其他项目（零），剩余时间和最低ID仍是堆或优先级队列中的peek操作，同时保留了堆属性。请注意，优先级队列不适用于搜索（哈希表或二进制搜索树可以做到这一点）。但用于在保持堆属性的同时进行插入或删除。您应该仅使用remove和O(log n) API方法来实现所需的操作，同时确保为优先级队列设计的时间复杂度（）。

    2025-04-13 15:07:05 1条评论

相关问题