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

Time Complexity: Priority Queue Introduction and Concept

O(n log n)

Understanding Time Complexity

We want to understand how the time to add or remove items from a priority queue changes as the number of items grows.

How does the queue handle tasks with different priorities efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class PriorityQueue {
  private items: number[] = [];

  enqueue(element: number) {
    this.items.push(element);
    this.items.sort((a, b) => b - a); // highest priority first
  }

  dequeue() {
    return this.items.pop();
  }
}
    

This code adds elements to a queue and keeps them sorted so the highest priority is always removed first.

Identify Repeating Operations

• Primary operation: Sorting the array after each insertion.
• How many times: Sorting happens every time we add an element.

How Execution Grows With Input

Sorting takes more time as the list grows because it compares many elements.

Input Size (n)	Approx. Operations
10	About 30-50 comparisons
100	About 500-700 comparisons
1000	About 10,000-15,000 comparisons

Pattern observation: Operations grow quickly, roughly proportional to n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means adding an item takes longer as the queue grows, but not as fast as checking every pair of items.

Common Mistake

[X] Wrong: "Adding an item is always quick because we just push it to the list."

[OK] Correct: After adding, the list must be sorted to keep priorities correct, which takes extra time.

Interview Connect

Understanding how priority queues manage time helps you explain efficient task handling in many programs.

Self-Check

"What if we used a heap data structure instead of sorting the array every time? How would the time complexity change?"

Practice

1. What is the main feature that distinguishes a Priority Queue from a regular queue?

easy

A. It does not allow duplicate elements

B. Elements are always dequeued in the order they were inserted

C. Elements are dequeued based on their priority, not just order of insertion

D. It only stores elements of the same value

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Identify priority queue behavior

   A priority queue removes elements based on their priority, not just insertion order.

3. Final Answer:

   Elements are dequeued based on their priority, not just order of insertion -> Option C

4. Quick Check:

   Priority Queue = dequeue by priority [OK]

Hint: Priority queues remove highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue sorts elements permanently
• Assuming priority queue disallows duplicates

2. Which of the following is the correct TypeScript syntax to declare a priority queue class with a generic type T?

easy

A. let PriorityQueue = <T>() => { }

B. class PriorityQueue<T> { constructor() {} }

C. function PriorityQueue<T>() { }

D. interface PriorityQueue<T> { new(): T }

Solution

1. Step 1: Recall TypeScript class syntax

   Classes are declared with the class keyword and generics use angle brackets after the class name.

2. Step 2: Check each option

   class PriorityQueue<T> { constructor() {} } correctly declares a generic class with constructor. Others use function, arrow function, or interface incorrectly for class declaration.

3. Final Answer:

   class PriorityQueue<T> { constructor() {} } -> Option B

4. Quick Check:

   Generic class syntax = class Name<T> {} [OK]

Hint: Use class with <T> for generics in TypeScript [OK]

Common Mistakes:

• Using function instead of class for data structure
• Confusing interface with class declaration
• Incorrect generic syntax placement

3. Consider this TypeScript code using a simple priority queue that stores numbers with lower values having higher priority:

class PriorityQueue {
  private data: number[] = [];
  enqueue(value: number) {
    this.data.push(value);
    this.data.sort((a, b) => a - b);
  }
  dequeue() {
    return this.data.shift();
  }
}

const pq = new PriorityQueue();
pq.enqueue(5);
pq.enqueue(1);
pq.enqueue(3);
const first = pq.dequeue();
const second = pq.dequeue();

What are the values of first and second?

medium

A. [5, 1]

B. [5, 3]

C. [3, 5]

D. [1, 3]

Solution

1. Step 1: Trace enqueue operations

   Values 5, 1, 3 are added. After each enqueue, array is sorted ascending: [5], then [1,5], then [1,3,5].

2. Step 2: Trace dequeue operations

   Dequeue removes first element (lowest value): first = 1, second = 3.

3. Final Answer:

   [1, 3] -> Option D

4. Quick Check:

   Sorted ascending, dequeue removes smallest [OK]

Hint: Sort ascending, dequeue removes first element [OK]

Common Mistakes:

• Assuming dequeue removes largest value
• Not sorting after enqueue
• Confusing shift() with pop()

4. The following TypeScript code for a priority queue has a bug. What is the bug?

class PriorityQueue {
  private data: number[] = [];
  enqueue(value: number) {
    this.data.push(value);
  }
  dequeue() {
    return this.data.pop();
  }
}

medium

A. Dequeue removes the last element, not the highest priority

B. Enqueue does not add elements to the queue

C. Data array is not initialized

D. Class is missing a constructor

Solution

1. Step 1: Analyze enqueue method

   Enqueue adds elements to the end of the array correctly.

2. Step 2: Analyze dequeue method

   Dequeue uses pop(), which removes last element, not necessarily highest priority.

3. Final Answer:

   Dequeue removes the last element, not the highest priority -> Option A

4. Quick Check:

   pop() removes last, not priority element [OK]

Hint: Dequeue should remove highest priority, not last element [OK]

Common Mistakes:

• Using pop() instead of shift() or priority removal
• Ignoring sorting or priority logic
• Assuming push() sorts automatically

5. You want to implement a priority queue in TypeScript where higher numbers have higher priority. Which approach correctly maintains the queue so that dequeue() always removes the highest number efficiently?

hard

A. Store elements in an array and sort descending after each enqueue, then remove first element on dequeue

B. Store elements in an array and sort ascending after each enqueue, then remove first element on dequeue

C. Store elements in an unsorted array and remove the maximum element by scanning on each dequeue

D. Store elements in a linked list without sorting and remove the first element on dequeue

Solution

1. Step 1: Understand priority requirement

   Higher numbers have higher priority, so dequeue should remove the largest number.

2. Step 2: Evaluate each approach

   Store elements in an array and sort ascending after each enqueue, then remove first element on dequeue removes the smallest (lowest priority). Store elements in an array and sort descending after each enqueue, then remove first element on dequeue places largest first for efficient removal. Store elements in an unsorted array and remove the maximum element by scanning on each dequeue is correct but inefficient O(n). Store elements in a linked list without sorting and remove the first element on dequeue follows insertion order, not priority.

3. Final Answer:

   Store elements in an array and sort descending after each enqueue, then remove first element on dequeue -> Option A

4. Quick Check:

   Sort descending + remove first = highest priority [OK]

Hint: Sort descending, dequeue removes first for highest priority [OK]

Common Mistakes:

• Sorting ascending but removing wrong end
• Not sorting and scanning entire array on dequeue
• Using linked list without priority order