PROSAGA码农传奇-调度引擎-通过密钥区分优先级队列堆的时间复杂度

<div class =“post-text”itemprop =“text”>
  <P>
    一个
     <code>
      java.util.PriorityQueue
    </code>
     （的
     <code>
      Task
    </code>
     实例）
    <a href="https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html#PriorityQueue-java.util.Comparator-" rel="nofollow noreferrer">
      构造函数
    </A>
     可以拿一个
     <code>
      Comparator
    </code>
     这可以考虑到
     <code>
      Task#Priority
    </code>
     和
     <code>
      Task#ID
    </code>
     这意味着（优先级）关系可以根据（假设）唯一的ID来打破。所以，一个任务
     <code>
      t1(Priority=5, ID=100, Time=10)
    </code>
     可以在任务之前（即优先于）
     <code>
      t2(Priority=5, ID=110, Time=10)
    </code>
    。
  </p>
  <P>
    删除具有最高优先级的此类项目（位于根目录）以及可能具有相同优先级的其他项目，零剩余时间
    的<strong>
      和
    </强>
     最低ID仍然是
     <code>
      O(log(n))
    </code>
     在保持堆属性的同时在堆或优先级队列中进行操作。请注意，优先级队列不是很好
    <EM>
      搜索
    </EM>
     （哈希表或二进制搜索树做得那么好）;但是在保持堆属性的同时插入或删除。你应该只使用
    <a href="https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html#peek--" rel="nofollow noreferrer">
       <code>
        peek
      </code>
    </A>
     和
    <a href="https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#remove--" rel="nofollow noreferrer">
       <code>
        remove
      </code>
    </A>
     API方法实现您需要的操作，同时确保时间复杂度（
     <code>
      O(log n)
    </code>
    ）优先级队列的设计目的。
  </p>
</DIV>