Priority Queue - Implementation - Usual Implementation

Usual Implementation

To improve performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals, and O(n) to build initially. Alternatively, when a self-balancing binary search tree is used, insertion and removal also take O(log n) time, although building trees from existing sequences of elements takes O(n log n) time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries.

Note that from a computational-complexity standpoint, priority queues are congruent to sorting algorithms. See the next section for how efficient sorting algorithms can create efficient priority queues.

There are several specialized heap data structures that either supply additional operations or outperform these approaches. The binary heap uses O(log n) time for both operations, but also allow queries of the element of highest priority without removing it in constant time. Binomial heaps add several more operations, but require O(log n) time for requests. Fibonacci heaps can insert elements, query the highest priority element, and increase an element's priority in amortized constant time though deletions are still O(log n)). Brodal queues can do this in worst-case constant time.

While relying on a heap is a common way to implement priority queues, for integer data, faster implementations exist. This can even apply to data-types that have a finite range, such as floats:

  • When the set of keys is {1, 2, ..., C}, a van Emde Boas tree would support the minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor and successor operations in time, but has a space cost for small queues of about O(2m/2), where m is the number of bits in the priority value.
  • The Fusion tree algorithm by Fredman and Willard implements the minimum operation in O(1) time and insert and extract-min operations in time.

For applications that do many "peek" operations for every "extract-min" operation, the time complexity for peek actions can be reduced to O(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. For insertion, this adds at most a constant cost, since the newly inserted element is compared only to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is typically cheaper than the deletion cost, so overall time complexity is not significantly impacted.

Read more about this topic:  Priority Queue, Implementation

Famous quotes containing the word usual:

    As usual the Liberals offer a mixture of sound and original ideas. Unfortunately none of the sound ideas is original and none of the original ideas is sound.
    Harold MacMillan (1894–1986)