Priority Queue Introduction and Concept in DSA Python - Time & Space Complexity

Time Complexity: Priority Queue Introduction and Concept

O(log n)

Understanding Time Complexity

We want to understand how the time to add or remove items in a priority queue changes as we add more items.

How does the work grow when the queue gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import heapq

pq = []
heapq.heappush(pq, 5)  # Add item with priority 5
heapq.heappush(pq, 1)  # Add item with priority 1
heapq.heappush(pq, 3)  # Add item with priority 3
smallest = heapq.heappop(pq)  # Remove smallest item
print(smallest)

This code adds items to a priority queue and removes the smallest item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing an item in the heap (priority queue).
• How many times: Each add or remove operation works by moving items up or down the heap tree, which takes steps proportional to the height of the tree.

How Execution Grows With Input

As the number of items (n) grows, the height of the heap grows slowly, about the logarithm of n.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly as the queue gets bigger, not directly with n but with log n.

Final Time Complexity

Time Complexity: O(log n)

This means adding or removing an item takes a small number of steps that grow slowly as the queue size grows.

Common Mistake

[X] Wrong: "Adding or removing items in a priority queue takes the same time no matter how many items are inside."

[OK] Correct: Actually, the time depends on the height of the heap, which grows with the number of items, so bigger queues take more steps.

Interview Connect

Understanding how priority queues work and their time costs helps you explain efficient ways to manage tasks by priority in real projects.

Self-Check

"What if we used a simple list and sorted it every time we add an item? How would the time complexity change?"