Priority Queue

Definition

Abstract Data Type

Priority queue: data structure storing elements with associated priorities. Removal: highest-priority element first. Ordering: not strictly FIFO or LIFO.

Priority Concept

Priority: numeric or comparable attribute. Determines processing order. Higher priority = earlier removal. Equal priorities: tie-breaking by insertion order or arbitrary.

Use Cases

Scheduling, graph algorithms, event simulation, bandwidth management, resource allocation, real-time systems.

Basic Operations

Insertion

Add element with priority. Maintains priority order internally.

Peek / Find-Min or Find-Max

Access element with highest priority without removal.

Deletion

Remove and return element with highest priority. Updates internal structure.

Change Priority

Modify priority of existing element. Requires repositioning.

Implementations

Array / List

Simple, unsorted array: insertion O(1), deletion O(n). Sorted array: insertion O(n), deletion O(1).

Linked List

Sorted linked list: insertion O(n), deletion O(1). Unsorted: insertion O(1), deletion O(n).

Heap

Binary heap: balanced binary tree with heap property. Insertion and deletion O(log n). Most common implementation.

Other Data Structures

Binomial heaps, Fibonacci heaps, pairing heaps: improved amortized complexities for specific operations.

Heap Structure

Binary Heap

Complete binary tree. Min-heap: parent ≤ children. Max-heap: parent ≥ children. Efficient priority queue base.

Heap Property

Order invariant enabling efficient retrieval of highest priority element. Maintained after insertions/deletions.

Array Representation

Binary heap stored in array. Parent and child indices calculated by simple formulas. Saves memory overhead of pointers.

Heapify Operation

Converts arbitrary array into heap. Bottom-up approach. Time complexity O(n).

Complexity Analysis

Time Complexity

Space Complexity

O(n) for all implementations storing n elements. Overhead depends on pointers or array structure.

Applications

CPU Scheduling

Operating systems use priority queues to schedule processes based on priority levels.

Graph Algorithms

Dijkstra’s shortest path, Prim’s MST algorithms rely on priority queues for selecting minimum-weight edges.

Event Simulation

Discrete event simulators use priority queues to manage future events by timestamp priority.

Data Compression

Huffman coding uses priority queues to build optimal prefix codes.

Network Routing

Priority queues optimize packet scheduling and bandwidth allocation.

Variants

Min-Priority Queue

Extracts minimum element first. Common in shortest path algorithms.

Max-Priority Queue

Extracts maximum element first. Used in scheduling where highest priority means largest value.

Double-Ended Priority Queue

Supports extraction of both minimum and maximum elements efficiently.

Concurrent Priority Queue

Thread-safe variants designed for multi-threaded environments. Use locks or lock-free structures.

Comparison with Queues

FIFO vs Priority Order

Standard queues process elements in first-in-first-out order. Priority queues process based on priority.

Use Cases Differentiation

Queues: linear tasks, buffering. Priority queues: scheduling, optimization problems.

Operational Complexity

Queues: O(1) for enqueue/dequeue. Priority queues: typically O(log n) due to ordering requirements.

Common Algorithms

Dijkstra’s Algorithm

Uses min-priority queue to select next vertex with minimum tentative distance. Priority updates frequent.

Prim’s Algorithm

Minimum spanning tree construction uses priority queue to pick edges with smallest weights.

Huffman Coding

Builds tree by repeatedly extracting two lowest-frequency elements from min-priority queue.

Heapify

Algorithm to build heap from unordered array. Bottom-up approach with O(n) complexity.

function heapify(array): n = length(array) for i = floor(n/2) down to 0: siftDown(array, i, n)

Limitations

Complexity Overhead

Insertion and deletion more expensive than simple queues. Not suitable for all real-time systems.

Memory Usage

Pointer-based implementations add overhead. Arrays require contiguous memory.

Priority Changes

Updating priorities can be complex and costly. Not always supported efficiently.

Non-Determinism

Equal priorities may lead to arbitrary removal order, potentially problematic for fairness.

Optimizations

Fibonacci Heap

Amortized O(1) insertion and decrease-key, O(log n) deletion. Used in advanced graph algorithms.

Pairing Heap

Simpler alternative to Fibonacci heap with good practical amortized time.

Lazy Deletion

Defers deletions to reduce immediate overhead. Useful in concurrent or amortized contexts.

Array-Based Implementations

Cache-friendly layout improves runtime performance of heaps.

Code Example

Binary Heap Insert

function insert(heap, element): heap.append(element) current = heap.size - 1 while current > 0 and heap[parent(current)] > heap[current]: swap(heap[current], heap[parent(current)]) current = parent(current)

Extract Min

function extractMin(heap): if heap.size == 0: return error min = heap[0] heap[0] = heap[heap.size - 1] heap.pop() siftDown(heap, 0, heap.size) return min

References

• Williams, J.W.J., "Algorithm 232: Heapsort," Communications of the ACM, vol. 7, no. 6, 1964, pp. 347-348.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., "Introduction to Algorithms," MIT Press, 3rd Ed., 2009, pp. 153-181.
• Fredman, M.L., Tarjan, R.E., "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM, vol. 34, no. 3, 1987, pp. 596-615.
• Sedgewick, R., Wayne, K., "Algorithms," 4th Ed., Addison-Wesley, 2011, pp. 157-180.
• Knuth, D.E., "The Art of Computer Programming, Volume 3: Sorting and Searching," Addison-Wesley, 2nd Ed., 1998, pp. 120-130.