Priority Queues

  • Priority queue data structure is an abstract data type that provides a way to maintain a set of elements, each with an associated value called key.

  • There are two kinds of priority queues: a max-priority queue and a min-priority queue. In both kinds, the priority queue stores a collection of elements and is always able to provide the most “extreme” element, which is the only way to interact with the priority queue. For the remainder of this section, we will discuss max-priority queues. Min-priority queues are analogous.

Operations

  • A max-priority queue provides the following operations:

    • insert: add an element to the priority queue.

    • maxElement: return the largest element in the priority queue.

    • removeMaxElement: remove the largest element from the priority queue.

  • A max-priority queue can also provide these additional operations:

    • size: return the number of elements in the priority queue.

    • increaseKey: updates the key of an element to a larger value.

    • updatePriorities: assume the values of the keys have been changed and reorder the internal state of the priority queue.

  • The names of these methods may be different based on implementations, but all priority queues should provide a way to do these or similar operations.

Implementations

  • Let’s explore several possibilities for data structures we could use to implement a priority queue:

    • Unordered array

      A simple, yet inefficient implementation, as retrieving the max element would require searching the entire array.

    • Sorted array

      This is not a very efficient implementation either. Inserting a new element requires linearly searching the array for the correct position. Removing similarly requires a linear time: the rest of the elements need to be adjusted (shifted) into correct positions.

    • Hash table

      Although inserting into a hash table takes constant time (given a good hash function), finding the max element takes linear time. Therefore, this would be a poor choice for the underlying data structure.

    • Heap

      It turns out that that a heap makes an efficient priority queue.

  • Below is a summary of the complexities of the common operations on a priority queue:

    Operation Unordered array Sorted array Hash table Binary heap

    insert

    Θ(1)\Theta(1)

    Θ(N)\Theta(N)

    Θ(1)\Theta(1)

    Θ(log(N))\Theta(\log (N))

    maxElement

    Θ(N)\Theta(N)

    Θ(1)\Theta(1)

    Θ(N)\Theta(N)

    Θ(1)\Theta(1)

    removeMaxElement

    Θ(N)\Theta(N)

    Θ(1)\Theta(1)

    Θ(N)\Theta(N)

    Θ(log(N))\Theta(\log (N))

results matching ""

    No results matching ""