Skip to main content
Definition Website Computer and Technology

Priority Queue

Subject: Computer and Technology noun /praɪˈɔːr.ə.ti kjuː/ 1 definition

  1. Definition (noun)

    Entry #43 · Updated

    A 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 priority 2, and nightly analytics exports carry priority 10. 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.