Intro

Priority Queue is a Queue where:

1. every item in the queue has a priority, and
2. higher-priority items are dequeued before lower-priority items

Usage

• operating system schedulers may use priority queues to select the next process to run, ensuring high-priority tasks run before low-priority ones

Comparison

Advantages

• quickly access the highest-priority item
  • Priority Queues allow you to peek at the top item in O(1) while keeping other operations relatively cheap, O(log(n))

Disadvantages

• slow enqueues and dequeues
  • both operations take O(log(n)) time with priority queues, with normal first-in, first-out FIFO queues, these operations are O(1) time

Problems

• [ ]

Corner Cases

Implementation

Priority queues can be implemented using

Binary Heaps

• enqueue an item → add it to the heap using the priority as the key O(log n)
• peek at the highest priority item → look at the item at the top O(1)
• dequeue the highest priority item → remove the top item from the heap O(log n)

Sorted List

• enqueue an item → binary search to figure out where the new item should go, then scoot items over to make space for the new item O(n) since in the worst case, you have to scoot everything over to make room
• peek at the highest priority item → look at the item at index zero O(1)
• dequeue the highest priority item → scoot every item forward one index. O(n)

Sorted Linked List

• enqueue an item → walk through the linked list to figure out where the new item should go, then, reassign pointers to add the new item O(n)
• peek at the highest priority item → look at the item at the head of the linked list O(1)
• dequeue the highest priority item → update the linked list's head pointer to point to the second item (and deallocate the old head node, if you're using a language with manual memory management) O(1)

n is the number of elements in the priority queue

Algorithms

Dijkstra's Shortest-Path

A* search (a graph traversal algorithm like BFS)

Huffman codes (an encoding for data compression)

Patterns

Code

class Node:
    def __init__(self, val, priority):
        self.value = val
        self.priority = priority
        self.next = None

class Pqueue:
    def __init__(self):
        self.Front = None
        self.Rear = None

    def enqueue(self, val, priority=None):
        if self.empty() is True:
            self.Front = Node(val, priority)
            self.Rear = self.Front
            return
        inst = Node(val, priority)
        if inst.priority < self.Front.priority:
            inst.next = self.Front
            self.Front = inst
        elif inst.priority >= self.Rear.priority:
            self.Rear.next = inst
            self.Rear = self.Rear.next
        elif inst.priority == self.Front.priority:
            n = self.Front.next
            f = self.Front
            while n.priority == inst.priority:
                n = n.next
                f = f.next
            f.next = inst
            f.next.next = n
        else:
            f = self.Front.next
            n = f.next
            while n.priority <= inst.priority:
                n = n.next
                f = f.next
            f.next = inst
            f.next.next = n

    def dequeue(self):
        if self.empty() is True:
            print("Queue is empty")
            return -1
        elif self.Front == self.Rear:
            temp = self.Front.value
            self.Front = None
            self.Rear = None
            return temp
        else:
            temp = self.Front.value
            self.Front = self.Front.next
            return temp

    def front(self):
        if self.empty() is True:
            print("Queue empty")
            return -1
        else:
            return self.Front.value

    def rear(self):
        if self.empty() is True:
            print("Queue empty")
            return -1
        else:
            return self.Rear.value

    def empty(self):
        if self.Rear is None:
            return True
        else:
            return False

    def display(self):
        print("The Queue")
        if self.empty() is True:
            print("Queue empty")
        elif self.Front == self.Rear:
            print("val priority")
            print(self.Front.value, "\\t", self.Front.priority,  "<== FRONT <== REAR")
        else:
            i = self.Front.next
            print("val priority")
            print(self.Front.value, "\\t", self.Front.priority, "<== FRONT")
            while i is not self.Rear:
                print(i.value, "\\t", i.priority)
                i = i.next
            print(self.Rear.value, "\\t", self.Rear.priority, "<== REAR")
        print("Queue Over")

Resources