Priority Queue Introduction and Concept in DSA Typescript - Execution Trace

Concept Flow - Priority Queue Introduction and Concept

Start with empty queue

↓

Insert element with priority

↓

Place element in queue based on priority

↓

Remove element with highest priority

↓

Return removed element

↓

Repeat insert/remove as needed

Shows how elements are added and removed in order of priority in a priority queue.

Execution Sample

DSA Typescript

class PriorityQueue {
  private items: {value: string, priority: number}[] = [];

  enqueue(value: string, priority: number) {
    // Insert element based on priority
  }

  dequeue() {
    // Remove highest priority element
  }
}

This code defines a priority queue where elements are inserted and removed based on their priority.

Execution Table

Step	Operation	Nodes in Queue	Pointer Changes	Visual State
1	Start with empty queue	[]	head=null	null
2	Enqueue 'A' with priority 2	[{A,2}]	head -> A	A(2) -> null
3	Enqueue 'B' with priority 1	[{B,1}, {A,2}]	head -> B	B(1) -> A(2) -> null
4	Enqueue 'C' with priority 3	[{B,1}, {A,2}, {C,3}]	head -> B	B(1) -> A(2) -> C(3) -> null
5	Dequeue (remove highest priority)	[{A,2}, {C,3}]	head -> A	A(2) -> C(3) -> null
6	Dequeue (remove highest priority)	[{C,3}]	head -> C	C(3) -> null
7	Dequeue (remove highest priority)	[]	head=null	null
8	Dequeue on empty queue	[]	head=null	null

💡 Queue is empty, no more elements to dequeue

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
items	[]	[{A,2}]	[{B,1},{A,2}]	[{B,1},{A,2},{C,3}]	[{A,2},{C,3}]	[{C,3}]	[]	[]
head	null	A	B	B	A	C	null	null

Key Moments - 3 Insights

Why does 'B' with priority 1 come before 'A' with priority 2 in the queue?

Because lower priority number means higher priority, so 'B' (priority 1) is placed before 'A' (priority 2), as shown in step 3 of the execution_table.

What happens when we dequeue from an empty queue?

The queue remains empty and head stays null, as shown in step 8 of the execution_table, meaning no element can be removed.

Why do we insert new elements in order based on priority?

To ensure dequeue always removes the element with the highest priority (lowest number), as seen in steps 2-4 where elements are placed in priority order.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after step 3?

A B(1) -> A(2) -> null

B A(2) -> null

C A(2) -> B(1) -> null

D B(1) -> null

💡 Hint

Check the 'Visual State' column for step 3 in the execution_table.

At which step does the queue become empty after dequeues?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Nodes in Queue' column to see when it becomes [].

If we enqueue an element with priority 0, where will it be placed?

A At the end of the queue

B At the beginning of the queue

C In the middle of the queue

D It will not be added

💡 Hint

Remember lower priority number means higher priority, so it goes before all others.

Concept Snapshot

Priority Queue stores elements with priorities.
Lower number means higher priority.
Enqueue inserts element in order.
Dequeue removes highest priority element.
Used where order matters beyond arrival time.

Full Transcript

A priority queue is a special list where each item has a priority number. Items with lower numbers have higher priority. When adding (enqueue), the item is placed so the list stays sorted by priority. When removing (dequeue), the item with the highest priority (lowest number) is taken out first. This example shows adding items A, B, C with priorities 2, 1, 3 respectively. B comes before A because 1 is less than 2. Removing items takes them out in priority order until the queue is empty.

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