Priority Queues

Summary of what priority queues are, how they are implemented, time complexity….copied from various online sources and placed here for my own convenience.

What is it?

Priority Queue data structure is a special queue in which the elements are present not as per FIFO order but according to the natural elements or any custom comparator used during queue creation.

• For non-comparable objects, we cannot create a priority queue.
• The head or front of the queue contains the least element as per the natural ordering. When we do remove or poll, the head element will be removed.
• Not thread safe.
• No null elements

Implementation

A priority queue can be implemented using an array, a Linked List or a heap data structure, or a binary search tree. Out of these options, the binary heap data structure is an efficient implementation.

Binary heap (Start from a binary tree and attempt to correct it to make it become max or min heap property)

Max heap: The key of each node is larger than or equal to the keys in its children.

Time complexity (Using binary heap)

1. The time complexity of Priority Queue for insertion(enqueue) and deletion (dequeue) methods, is O(log(n)).
2. Priority Queue has O(n) complexity for remove as well as contains methods.

Insertion O(logn)

Add a new node at the end, swim it up.

Deletion O(logn)

Select the element to be deleted. Swap with the last element. Remove the last element. Heapify the tree.

Max O(1)

Return element with the highest priority, which is the root.

Extract Max O(logn)

Return and remove the highest priority element.

Remove the root, exchange last element with root and sink it down.

Binary heap build: O(n)

• Will not elaborate….