I came along learning built-in types in C#, and now interested in PriorityQueue<TElement, TPriority> introduced in .NET 6
I'm wondering what is the time complexity for the common operations like:
Thanks!
The PriorityQueue class is implemented as a min heap:
Implements an array-backed, quaternary min-heap.
Moreover the source code is on github.
We can then know the time complexities are as follows:
Heapify an unordered array:
If the collection is passed to the constructor, the time complexity will be O(n). This is already suggested by the comment in the documentation:
Constructs the heap using a heapify operation, which is generally faster than enqueuing individual elements sequentially.
...but confirmed by the code we find for Heapify. It implements the O(n) algorithm mentioned at Wikipedia.
Dequeue an element
Wikipedia describes the algorithm and concludes:
the delete operation has a time complexity relative to the height of the tree, or O(log n).
It is this algorithm that is implemented by Dequeue.
Enqueue an element
Wikipedia describes the algorithm and concludes:
the insertion operation has a worst-case time complexity of O(log n). For a random heap, and for repeated insertions, the insertion operation has an average-case complexity of O(1)
It is this algorithm that is implemented by Enqueue.