Priority Queue

Another type of queue is a priority queue. These behave very similarly to standard queues with the exception that rather than being First-In-First-Out, the order in which items are removed is determined by a predefined priority function. There are multiple ways to implement this. A somewhat slow example using Linked Lists is shown below. It is unlikely that anyone would use such an implementation in a production scenario; however, it is a useful learning tool for understanding how Priority Queues work at a conceptual level.

Asymptotic Complexity

  • Insert: $O(n)$
  • Extract: $O(1)$
  • Find: $O(1)$

Pseudo Code


    if item1 and item2 are equal
        return 0
    if item1 should be before item2
        return 1
    if item1 should be after item2
        return -1


    for each item in the list:
        if prority_function(new_item, item) = 1
            insert new_item before item
            break out of loop

    Remove item from the head of the list and returns it

    Return item from the head without removing it from the list

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions