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

priority_function:
    item1
    item2

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

insert:
    new_item

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

extract:
    Remove item from the head of the list and returns it

find:
    Return item from the head without removing it from the list

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions