Priority Queue Introduction and Concept in DSA Typescript

Mental Model

A priority queue is like a line where people with higher importance get served first, no matter when they arrive.

Analogy: Imagine a hospital emergency room where patients with more serious conditions are treated before others, even if they arrived later.

Priority Queue:
[Patient with priority 5] -> [Patient with priority 3] -> [Patient with priority 1] -> null
↑ front (highest priority)

Dry Run Walkthrough

Input: Insert patients with priorities 3, 5, 1 into an empty priority queue

Goal: Keep the queue ordered so the patient with the highest priority (largest number) is always at the front

Step 1: Insert patient with priority 3 into empty queue

[3] -> null ↑ front

Why: First patient becomes the front as queue was empty

Step 2: Insert patient with priority 5, which is higher than 3

[5] -> [3] -> null ↑ front

Why: New patient has higher priority, so placed at front

Step 3: Insert patient with priority 1, which is lower than 3 and 5

[5] -> [3] -> [1] -> null ↑ front

Why: New patient has lowest priority, so placed at the end

Result:

[5] -> [3] -> [1] -> null ↑ front

Annotated Code

DSA Typescript

class Node {
  priority: number;
  next: Node | null;
  constructor(priority: number) {
    this.priority = priority;
    this.next = null;
  }
}

class PriorityQueue {
  front: Node | null;
  constructor() {
    this.front = null;
  }

  enqueue(priority: number): void {
    const newNode = new Node(priority);
    if (!this.front || priority > this.front.priority) {
      newNode.next = this.front; // place new node at front
      this.front = newNode; // update front pointer
      return;
    }

    let current = this.front;
    while (current.next && current.next.priority >= priority) {
      current = current.next; // move forward to find correct spot
    }

    newNode.next = current.next; // insert new node
    current.next = newNode;
  }

  printQueue(): void {
    let current = this.front;
    let result = '';
    while (current) {
      result += `[${current.priority}] -> `;
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

// Driver code
const pq = new PriorityQueue();
pq.enqueue(3);
pq.enqueue(5);
pq.enqueue(1);
pq.printQueue();

if (!this.front || priority > this.front.priority) {

check if new node should be placed at front because queue is empty or new priority is highest

newNode.next = this.front; // place new node at front this.front = newNode; // update front pointer

insert new node at front and update front pointer

while (current.next && current.next.priority >= priority) { current = current.next; // move forward to find correct spot }

traverse queue to find correct position where new node fits priority order

newNode.next = current.next; // insert new node current.next = newNode;

insert new node in the middle or end maintaining priority order

Output

[5] -> [3] -> [1] -> null

Complexity Analysis

Time: O(n) because in worst case we traverse the entire queue to find the correct position

Space: O(n) because each inserted element requires a new node in memory

vs Alternative: Compared to a simple queue where insertion is O(1) at the end, priority queue insertion is slower due to ordering but allows quick access to highest priority

Edge Cases

Empty queue

New node becomes the front immediately

DSA Typescript

if (!this.front || priority > this.front.priority) {

New node has highest priority

Inserted at front, pushing others back

DSA Typescript

if (!this.front || priority > this.front.priority) {

New node has lowest priority

Inserted at the end after traversing all nodes

DSA Typescript

while (current.next && current.next.priority >= priority) {

When to Use This Pattern

When you need to always process the most important item first, use a priority queue to keep elements sorted by priority automatically.

Common Mistakes

Mistake: Inserting new nodes without maintaining priority order
Fix: Traverse the queue to find the correct position based on priority before inserting

Mistake: Not updating the front pointer when inserting at the front
Fix: Always update the front pointer when new node has highest priority

Summary

A priority queue stores elements so the highest priority is always served first.

Use it when order of processing depends on priority, not arrival time.

The key is inserting elements in order so the front always has the highest priority.

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