Priority Queue

DSA · Stacks and Queues

Theory

A priority queue always removes the item with the highest priority (or lowest value) first, regardless of insertion order. It is usually implemented with a binary heap, giving O(log n) insert and remove and O(1) peek. Python's heapq module provides a min-heap; negate values for a max-heap.

Why we use it

It always gives you the most urgent item quickly, without re-sorting the whole collection after every change.

When to use it

Use it for task schedulers, Dijkstra's shortest path, merging sorted lists, finding the top-k items, and event simulation.

How it works

  1. Insert items with priorities
  2. Store in a min-heap
  3. Remove? Yes: Pop the smallest priority (root). No: Peek at the root.
  4. Re-heapify in O(log n)
  5. Always serves the most urgent item

Syntax

import heapq
heapq.heappush(pq, (priority, item))   O(log n)
heapq.heappop(pq)                      O(log n)
pq[0]                                  O(1) peek

Example

# A simple priority queue using a sorted insert (works everywhere)
class PriorityQueue:
    def __init__(self):
        self.items = []
    def push(self, priority, task):
        i = 0
        while i < len(self.items) and self.items[i][0] <= priority:
            i += 1
        self.items.insert(i, (priority, task))
    def pop(self):
        return self.items.pop(0)

pq = PriorityQueue()
pq.push(3, "Reply to emails")
pq.push(1, "Fix production bug")
pq.push(2, "Code review")
while pq.items:
    print(pq.pop())
# In real Python code use heapq for O(log n) push/pop

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic