Priority Queue
Subject: Computer and Technology noun /praɪˈɔːr.ə.ti kjuː/ 1 definition
- data-structures
- abstract-data-types
- task-scheduling
- computer-science
-
Definition (noun)
Entry #43 · UpdatedA Priority Queue is an abstract data type that manages a collection of elements, each associated with a priority key, so that retrieval always returns the item with the highest (or lowest) priority rather than the oldest entry. By exposing core operations to insert elements, inspect the top-priority item, and extract it on demand, it ensures critical tasks are processed ahead of routine work regardless of arrival order. Unlike a standard First-In, First-Out (FIFO) queue that enforces strict sequential ordering, or a fully sorted array that maintains total order across every item, a priority queue maintains only partial order—typically via a heap—to guarantee fast access to the next most urgent element.
Common Types
Min-Priority Queue: Treats smaller numeric keys as higher urgency and always extracts the minimum-key element first, making it foundational for shortest-path algorithms like Dijkstra's and timer event wheels.
Max-Priority Queue: Treats larger numeric keys as higher urgency and always extracts the maximum-key element first, commonly used in job dispatchers, bandwidth allocation, and top-ranked candidate selection.
Indexed Priority Queue: Maps external element identifiers to their internal queue positions so callers can dynamically update an item's priority key or delete it in logarithmic time without linear scanning.
Double-Ended Priority Queue: Supports inspecting and extracting both the minimum-priority and maximum-priority elements from a single collection, typically implemented using a min-max heap or interval heap.
Example
A cloud background-worker service routes incoming jobs through a min-heap priority queue where password-reset emails carry priority
1, billing webhooks carry priority2, and nightly analytics exports carry priority10. Even if 5,000 analytics jobs are already queued, a newly submitted password-reset task bubbles to the root in O(log n) time and is dequeued immediately ahead of lower-priority work.