Priority Queue Introduction and Concept in DSA Typescript - Build from Scratch

Priority Queue Introduction and Concept

📖 Scenario: Imagine you are managing a hospital emergency room. Patients arrive with different levels of urgency. You want to help the most urgent patients first. This is like a priority queue where each patient has a priority number.

🎯 Goal: You will create a simple priority queue using an array of objects. Each object has a name and a priority. You will then select the patient with the highest priority to help first.

📋 What You'll Learn

Create an array called patients with exact patient names and priorities

Create a variable called highestPriority to track the highest priority found

Use a for loop with variables patient to find the patient with the highest priority

Print the name of the patient with the highest priority

💡 Why This Matters

🌍 Real World

Priority queues are used in hospitals, task schedulers, and anywhere urgent tasks must be handled first.

💼 Career

Understanding priority queues helps in software development roles that involve scheduling, resource management, and real-time systems.

1

Create the patient list

Create an array called patients with these exact objects: { name: 'Alice', priority: 2 }, { name: 'Bob', priority: 5 }, { name: 'Charlie', priority: 3 }

DSA Typescript

// Create the patients array with name and priority
// Your code here

Hint

Use square brackets [] to create an array. Each patient is an object with name and priority.

2

Set up the highest priority tracker

Create a variable called highestPriority and set it to 0 to start tracking the highest priority

DSA Typescript

const patients = [
  { name: 'Alice', priority: 2 },
  { name: 'Bob', priority: 5 },
  { name: 'Charlie', priority: 3 }
];
// Create highestPriority variable and set to 0
// Your code here

Hint

Use let to create a variable that can change later.

3

Find the patient with the highest priority

Use a for loop with variable patient to go through patients. Inside the loop, if patient.priority is greater than highestPriority, update highestPriority to patient.priority and save patient.name in a variable called highestPriorityPatient

DSA Typescript

const patients = [
  { name: 'Alice', priority: 2 },
  { name: 'Bob', priority: 5 },
  { name: 'Charlie', priority: 3 }
];

let highestPriority = 0;
// Use a for loop to find the patient with the highest priority
// Your code here

Hint

Use for (const patient of patients) to check each patient. Use if to compare priorities.

4

Print the patient with the highest priority

Print the text "Patient with highest priority: " followed by the variable highestPriorityPatient

DSA Typescript

const patients = [
  { name: 'Alice', priority: 2 },
  { name: 'Bob', priority: 5 },
  { name: 'Charlie', priority: 3 }
];

let highestPriority = 0;
let highestPriorityPatient = '';

for (const patient of patients) {
  if (patient.priority > highestPriority) {
    highestPriority = patient.priority;
    highestPriorityPatient = patient.name;
  }
}
// Print the patient with the highest priority
// Your code here

Hint

Use console.log to print the message and the patient's name.

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