Priority queue with heaps in Data Structures Theory - Time & Space Complexity

Time Complexity: Priority queue with heaps

O(log n)

Understanding Time Complexity

We want to understand how the time needed to manage a priority queue using a heap changes as the number of items grows.

Specifically, how fast can we add or remove items when the queue gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following heap operations.

// Insert an element into a max-heap
function insert(heap, value) {
  heap.push(value)               // Add at the end
  let i = heap.length - 1
  while (i > 0 && heap[parent(i)] < heap[i]) {
    swap(heap, i, parent(i))     // Move up if bigger than parent
    i = parent(i)
  }
}

// Remove the max element from a max-heap
function extractMax(heap) {
  if (heap.length === 0) return null
  let max = heap[0]
  heap[0] = heap.pop()           // Replace root with last element
  if (heap.length > 0) {
    heapify(heap, 0)             // Fix heap property downwards
  }
  return max
}

This code shows how we add a new item and remove the largest item in a heap-based priority queue.

Identify Repeating Operations

Look at the loops that move elements up or down the heap.

• Primary operation: Swapping elements while moving up (insert) or down (extractMax) the heap.
• How many times: At most, the number of swaps equals the height of the heap, which grows as the heap grows.

How Execution Grows With Input

As the number of items n increases, the heap becomes taller, but not by much.

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

Pattern observation: The number of swaps grows slowly, roughly with the height of the heap, which increases logarithmically as the input size grows.

Final Time Complexity

Time Complexity: O(log n)

This means adding or removing an item takes time that grows slowly, roughly proportional to the number of times you can halve the number of items.

Common Mistake

[X] Wrong: "Adding or removing items in a heap is as slow as scanning all items, so it takes O(n) time."

[OK] Correct: The heap structure keeps items partially sorted in a tree shape, so operations only need to move along the height of the tree, not all items.

Interview Connect

Understanding heap operations and their time complexity shows you can work with efficient data structures that handle priority tasks quickly, a useful skill in many coding challenges.

Self-Check

"What if we used a simple unsorted list instead of a heap? How would the time complexity for adding and removing the highest priority item change?"