.NET 6中PriorityQueue常见操作的时间复杂度咨询

无序数组堆化（Heapify an unordered array） #

PriorityQueue内部基于二叉堆实现。当通过包含初始元素的集合实例化队列时，会执行堆化操作——从最后一个非叶子节点开始，逐层向上调整堆结构。该操作的时间复杂度为 O(n)（n为元素总数），这比逐个插入元素的O(n log n)效率更高。

出队（Dequeue an element） #

出队时会取出优先级最高的元素，随后将堆的最后一个元素移至堆顶，并执行向下调整（sift down）来维护堆的性质。这个调整过程需要遍历二叉堆的高度（层级为log₂n），因此时间复杂度为 O(log n)。

入队（Enqueue an element） #

入队操作是将新元素添加到堆的末尾，然后通过向上调整（sift up）找到它在堆中的正确位置。调整过程同样涉及堆的高度层级，所以时间复杂度为 O(log n)。

内容的提问来源于stack exchange，提问作者mexanichp