Priority Queue Introduction and Concept in DSA C - 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 from 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.

// Insert an element into a priority queue implemented as a binary heap
void insert(int heap[], int *size, int value) {
    int i = (*size)++;
    while (i > 0 && value > heap[(i - 1) / 2]) {
        heap[i] = heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    heap[i] = value;
}
    

This code adds a new value to a max-heap priority queue by moving it up until the heap property is restored.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves the new value up the heap.
• How many times: It runs at most once per level of the heap, moving from the bottom to the top.

How Execution Grows With Input

As the number of items (n) grows, the heap gets taller, so the number of steps to move up grows slowly.

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

Pattern observation: The steps grow slowly, roughly with the height of the heap, which increases as the logarithm of n.

Final Time Complexity

Time Complexity: O(log n)

This means adding an item takes time that grows slowly as the queue gets bigger, only about the height of the heap.

Common Mistake

[X] Wrong: "Adding an item always takes the same time no matter how big the queue is."

[OK] Correct: Because the new item may need to move up many levels to keep the order, so bigger queues can take more steps.

Interview Connect

Knowing how priority queues work and their time costs helps you explain efficient ways to manage tasks by importance, a common real-world problem.

Self-Check

"What if we used a simple unsorted array instead of a heap? How would the time complexity of adding and removing items change?"