✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-063

Priority Queues

A priority queue is an abstract data type in which elements are removed according to their priority rather than strictly according to their insertion order. Higher-priority or lower-priority elements are selected first depending on the chosen convention.

Explanation

Overview

A priority queue stores elements together with priority information. Its removal operation selects an element according to the priority ordering, and elements with equal priority are handled according to the implementation's tie-breaking policy.

Purpose

Priority queues are used when some tasks, events, or values must be processed before others based on importance, urgency, distance, cost, or another ranking criterion.

Key concepts

name: Core idea; description: The central focus of priority queues is the capability described here: A priority queue is an abstract data type in which elements are removed according to their priority rather than strictly according to their insertion order. Higher-priority or lower-priority elements are selected first depending on the chosen convention.; name: Problem context; description: Priority Queues is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using priority queues, check its assumptions, input requirements, expected output, and resource constraints.

Time complexity

unsortedArrayInsert: O(1); unsortedArrayPeek: O(n); unsortedArrayExtract: O(n); binaryHeapInsert: O(log n); binaryHeapPeek: O(1); binaryHeapExtract: O(log n)

Space complexity

O(n) for n stored elements in common array, heap, or tree implementations.

Example

items: task: Task A; priority: 2; task: Task B; priority: 5; queueType: Max-priority queue; removalOrder: Task B; Task A; explanation: Task B is removed first because it has the largest priority value. Task A follows, and Task C is removed last.

Advantages

Processes important tasks before less important tasks.; Supports efficient selection of minimum or maximum priority elements.; Useful in scheduling and graph algorithms.; Binary heaps provide efficient insertion and extraction.; Can represent event-driven processing systems.

Example or application

Items

TaskPriority

Task A

2

Task B

5

Task C

1

Queue Type

Max-priority queue

Removal Order

  • Task B

  • Task A

  • Task C

Explanation

Task B is removed first because it has the largest priority value. Task A follows, and Task C is removed last.

Definition

A priority queue stores elements together with priority information. Its removal operation selects an element according to the priority ordering, and elements with equal priority are handled according to the implementation's tie-breaking policy.

Purpose

Priority queues are used when some tasks, events, or values must be processed before others based on importance, urgency, distance, cost, or another ranking criterion.

Core Principle

The next element removed is determined by priority rather than ordinary FIFO order. The exact meaning of higher priority must be defined by the application.

Priority Types

NameDescription

Min-Priority Queue

Removes the element with the smallest priority value first.

Max-Priority Queue

Removes the element with the largest priority value first.

Main Operations

  • Insert: Adds an element with an associated priority.

  • Peek: Returns the highest-priority element without removing it.

  • Extract-Min: Removes and returns the element with the smallest priority in a min-priority queue.

  • Extract-Max: Removes and returns the element with the largest priority in a max-priority queue.

  • Change-Priority: Updates an element's priority when supported.

  • IsEmpty: Checks whether the priority queue contains any elements.

Implementation Methods

NameDescription

Unsorted Array or List

Insertion is simple, but finding the highest-priority element requires scanning the collection.

Sorted Array or List

The elements are maintained in priority order. Insertion may require shifting elements, while access to the selected end can be efficient.

Binary Heap

A complete binary tree commonly represented by an array. A min-heap or max-heap keeps the selected priority element at the root.

Balanced Search Tree

A balanced tree can maintain priority ordering and support insertion, removal, and searching operations efficiently.

Binary Heap Principle

In a min-heap, each parent has a priority value no greater than its children. In a max-heap, each parent has a priority value no smaller than its children. This property places the selected extreme value at the root.

Time Complexity

Unsorted Array Insert

O(1)

Unsorted Array Peek

O(n)

Unsorted Array Extract

O(n)

Binary Heap Insert

O(log n)

Binary Heap Peek

O(1)

Binary Heap Extract

O(log n)

Binary Heap Build

O(n) using bottom-up heap construction

Balanced Tree Insert

O(log n) when the tree remains balanced

Balanced Tree Remove Extreme

O(log n) when the tree remains balanced

Space Complexity

O(n) for n stored elements in common array, heap, or tree implementations.

Advantages

  • Processes important tasks before less important tasks.

  • Supports efficient selection of minimum or maximum priority elements.

  • Useful in scheduling and graph algorithms.

  • Binary heaps provide efficient insertion and extraction.

  • Can represent event-driven processing systems.

Limitations

  • Does not preserve ordinary insertion order across different priorities.

  • Equal-priority ordering may require additional handling.

  • Priority updates can require restructuring.

  • The best implementation depends on the required operation pattern.

Stability Consideration

A priority queue is not necessarily stable. If equal-priority elements must be processed in insertion order, the implementation can include a sequence number or another explicit tie-breaking rule.

Common Applications

  • CPU and process scheduling

  • Dijkstra's shortest-path algorithm

  • A* search

  • Event-driven simulation

  • Network traffic management

  • Task prioritization

  • Huffman coding

  • Operating-system resource scheduling

Implementation Considerations

  • Define whether smaller or larger values represent higher priority.

  • Choose an implementation based on insertion, extraction, and update requirements.

  • Handle equal priorities consistently.

  • Maintain heap or tree ordering after modifications.

  • Avoid changing an element's priority without restoring the required ordering.

Learning Objectives

  • Explain priority-based processing.

  • Distinguish min-priority and max-priority queues.

  • Understand common priority-queue operations.

  • Compare array, heap, and tree implementations.

  • Recognize priority queues in scheduling and graph algorithms.

Key Takeaways

  • A priority queue removes elements according to priority.

  • Min-priority queues select the smallest priority value.

  • Max-priority queues select the largest priority value.

  • Binary heaps commonly support O(log n) insertion and extraction.

  • Equal-priority ordering requires an explicit policy when stability matters.

Related Topics

  • Introduction to Queues

  • Queue Operations — Enqueue and Dequeue

  • Circular Queues

  • Double-Ended Queues (Deque)

  • Binary Heaps

  • Dijkstra's Algorithm

  • A* Search

Key Concepts

NameDescription

Core idea

The central focus of priority queues is the capability described here: A priority queue is an abstract data type in which elements are removed according to their priority rather than strictly according to their insertion order. Higher-priority or lower-priority elements are selected first depending on the chosen convention.

Problem context

Priority Queues is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using priority queues, check its assumptions, input requirements, expected output, and resource constraints.

Practice Questions

QuestionAnswer

What is the main purpose of priority queues?

A priority queue is an abstract data type in which elements are removed according to their priority rather than strictly according to their insertion order. Higher-priority or lower-priority elements are selected first depending on the chosen convention.

What should be checked before applying priority queues?

For priority queues, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of priority queues be validated?

Trace a representative priority queues case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures