Priority Queue

 

Priority Queue

 

 

A priority queue is a data structure similar to a regular queue, but with an additional feature: each element is associated with a priority level. In a standard queue, elements are added at the end and removed from the front in a first-in, first-out (FIFO) order. However, in a priority queue, elements are dequeued not strictly in the order they were enqueued but based on their priority.

 

Implementations of a Priority Queue

Priority queues can be implemented using various data structures:

1. Binary Heap (Min-Heap or Max-Heap): The most common implementation uses a heap, especially a binary heap. In a min-heap, the element with the smallest priority (or highest priority, depending on the application) is at the top, and in a max-heap, the element with the largest priority is at the top.
2. Binary Search Tree (BST): Priority queues can also be implemented using a balanced binary search tree (e.g., Red-Black Tree or AVL Tree), allowing for efficient insertions, deletions, and lookups based on priority.
3. Unordered List or Linked List: Elements can be stored in an unordered list where insertion is O(1), but finding the highest-priority element would take O(n).
4. Ordered List or Linked List: The list is kept sorted by priority. Finding the highest-priority element is O(1), but insertion takes O(n) to find the correct position in the sorted order.

 

Operations in a Priority Queue

§  Insert (Enqueue): Adds an element with a priority to the queue.

• Remove (Dequeue): Removes and returns the element with the highest priority.
• Peek: Returns the element with the highest priority without removing it.

 

Binary Heap

Heap has two properties

1.   Structure property

2.   Heap order property

 

Structure property

A heap is a binary tree that is completely filled, with possible exception of the bottom level which is filled from left to right. Such a tree is known as a complete binary tree.

Complete binary tree of height h has between 2^h and (2^h+1 – 1) nodes. Time complexity for any operation is O(log N). Since complete binary tree is regular it can be represented in an array.

For any element in array position i, the left child is in position 2i and right child is in the cell after the left child at position (2i+1). The parent is in position i/2

 

Heap order property

1.   A min-heap requires that each parent node is less than or equal to its children. This ensures that the minimum element is always at the root.

2.   A max-heap requires that each parent node is greater than or equal to its children, making the maximum element reside at the root.

 

Time Complexity

• Insert – (O(log n)) – Inserting an element involves placing it at the end of the array and then "bubbling up" or "heapifying up" the element by swapping it with its parent until the heap property is restored.
• Remove – (O(log n)) – Removing the highest-priority element (root) involves replacing it with the last element in the array, then "bubbling down" or "heapifying down" by repeatedly swapping with the smaller (or larger) child until the heap property is maintained.
• Peek – (O(1)) – Accessing the root (highest-priority element) without removing it is a constant-time operation.