Priority Queue Notes

What is a Priority Queue?

A priority queue is an abstract data type that behaves similarly to a normal queue but with priorities assigned to each element. The element with the highest priority is removed first. Elements are required to be comparable, so they are ordered either ascending or descending. For example, with values 1, 3, 4, 8, 14, 22 arranged in ascending order, 1 has the highest priority and 22 has the lowest.

Characteristics of a priority queue: every element has a priority, an element with higher priority is deleted before those with lower priority, and when two elements share the same priority they are arranged using the FIFO (first-in, first-out) principle. To illustrate, consider a priority queue containing 1, 3, 4, 8, 14, 22 arranged in ascending order. The operation poll() removes the element with the highest priority. In this setup, the element 1 is removed first. If we then add(2), the value 2, being the smallest among all numbers in the queue, obtains the highest priority and is placed at the front. A subsequent poll() would remove 2. If we then add(5), it is inserted after 4 because 5 is larger than 4 but less than 8, giving it the third-highest priority in the queue.

Types of Priority Queue

There are two types of priority queues based on how priority values map to ordering:

Ascending order priority queue: a lower numeric priority corresponds to higher priority. For example, with numbers 1 to 5 arranged in ascending order (1, 2, 3, 4, 5), the smallest number 1 has the highest priority.

Descending order priority queue: a higher numeric priority corresponds to higher priority. For example, with numbers 1 to 5 arranged in descending order (5, 4, 3, 2, 1), the largest number 5 has the highest priority.

Representation of Priority Queue

A priority queue can be represented using a one-way (singly linked) list. In this representation, there is an INFO list that contains the data elements, a PRN list that contains the priority numbers associated with each data element, and a LINK that holds the address of the next node. The construction proceeds step by step as follows. Step 1 assigns a lower priority number of 1 to data value 333, so 333 is inserted accordingly in the list. Step 2 introduces priority number 2, which has data values 222 and 111; these are inserted following the FIFO principle, so 222 comes before 111. Step 3 brings in priority 4 with data values 444, 555, and 777; these are inserted in FIFO order: 444, then 555, then 777. Step 4 adds priority 5 with the value 666 and inserts it at the end of the queue.

Implementation of Priority Queue

A priority queue can be implemented in four ways: using arrays, a linked list, a heap data structure, or a binary search tree. The heap data structure is the most efficient method for implementing a priority queue, so this topic focuses on heap-backed implementation.

What is a heap? A heap is a tree-based data structure that forms a complete binary tree and satisfies the heap property. If A is a parent node of B, then A is ordered with respect to B for all nodes A and B in a heap: the value of the parent node can be greater than or equal to the value of the child node (max-heap) or less than or equal to the value of the child node (min-heap). Therefore, there are two types of heaps: max-heap and min-heap. Both are binary heaps, as each node has at most two children.

Max heap: A max-heap is a heap in which the value of the parent node is greater than the values of its child nodes.
Min heap: A min-heap is a heap in which the value of the parent node is less than the values of its child nodes.

Priority Queue Operations

The common operations on a priority queue are insertion, deletion, and peek. To maintain the heap data structure, these operations must preserve the heap property as elements are added or removed.

Inserting an element in a priority queue (max heap)

When inserting an element into a priority queue implemented as a max-heap, the element is placed in the next available slot following a level-order (top-to-bottom, left-to-right) fill. If the element is not in the correct position with respect to its parent, it is swapped with the parent. This process continues until the element is in a position that satisfies the heap property relative to its ancestors.

Removing the maximum element from the priority queue

In a max-heap, the maximum element is at the root. When removing the root, the last element in the heap is moved to the root position to fill the gap, and then the heap property is restored by repeatedly swapping the new root with the larger of its children (to maintain a max-heap) until the property holds throughout the tree.

Heap Deletion Example

Suppose the heap is a Max-Heap as shown:

The element to be deleted is the root, 10. The last element is 4. Step 1: Replace the last element with the root and delete the original last element, yielding:

Step 2: Heapify the root. The final heap becomes:

This process restores the heap property after removing the maximum element.

Applications of Priority Queue

Priority queues have a wide range of applications. They are used in Dijkstra's shortest path algorithm, in Prim's algorithm, and in data compression techniques like Huffman coding. They are also employed in heap sort and in operating systems for tasks such as priority scheduling, load balancing, and interrupt handling.

Notation and Formulas (Key relations)

In array-based heap representations, the relation between indices is often used: the parent of index i is at floor(i/2), the left child is at index 2i, and the right child is at index 2i + 1. These relationships are summarized as:

$\text{parent}(i) = \left\lfloor \frac{i}{2} \right\rfloor, \quad \text{left}(i) = 2i, \quad \text{right}(i) = 2i + 1.$

For a max-heap, the heap property can be written as:

\forall i>1: \; A[\text{parent}(i)] \ge A[i],
and for a min-heap:

\forall i>1: \; A[\text{parent}(i)] \le A[i].

These properties ensure that the root always contains the maximum (in a max-heap) or the minimum (in a min-heap) element of the heap, and that every subtree is itself a heap.

Connections to broader concepts and real-world relevance

The priority queue concept aligns with foundational principles of ordering, efficiency, and resource management. Using a heap-based priority queue yields O(log n) time for insertion and removal, making it suitable for algorithms that repeatedly pick the next best item, such as Dijkstra’s algorithm (for selecting the next vertex with the smallest tentative distance) and Prim’s algorithm (for selecting the next edge with minimum weight). Huffman coding relies on a priority queue to repeatedly merge the two smallest-weight nodes. Heap sort uses a binary heap to sort elements in O(n log n) time. In operating systems, priority scheduling, load balancing, and interrupt handling benefit from fast priority-based decisions. Practically, equal-priority handling via FIFO ensures deterministic behavior in concurrent scenarios.

This set of notes consolidates the core ideas, definitions, procedures, and typical examples of priority queues, with emphasis on the heap-based implementation as the most efficient approach among the standard data structures.