Priority Queue Introduction and Concept in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Priority Queue insertion sequence?

Consider a min-priority queue implemented with a binary heap. Insert the elements 5, 3, 8, 1 in this order. What is the state of the heap array after all insertions?

DSA Typescript

class MinPriorityQueue {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    const element = this.heap[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.heap[parentIdx];
      if (element >= parent) break;
      this.heap[parentIdx] = element;
      this.heap[idx] = parent;
      idx = parentIdx;
    }
  }
}

const pq = new MinPriorityQueue();
pq.insert(5);
pq.insert(3);
pq.insert(8);
pq.insert(1);
console.log(pq.heap);

A [1, 3, 8, 5]

B [1, 5, 8, 3]

C [3, 1, 8, 5]

D [5, 3, 8, 1]

💡 Hint

Remember that in a min-heap, the smallest element is at the root and bubbleUp swaps elements upwards.

After inserting 5, heap is [5]. Insert 3, bubbleUp swaps 3 and 5 → [3,5]. Insert 8, no swap → [3,5,8]. Insert 1, bubbleUp swaps 1 with 3, then with root → [1,3,8,5].

❓ Predict Output

intermediate

What is the output after extracting min from this Priority Queue?

Given a min-priority queue with heap array [1, 3, 8, 5], what is the heap array after extracting the minimum element once?

DSA Typescript

class MinPriorityQueue {
  heap: number[] = [1, 3, 8, 5];

  extractMin() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return min;
  }

  sinkDown() {
    let idx = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (leftChild < element) swap = leftChildIdx;
      }
      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if ((swap === null && rightChild < element) || (swap !== null && rightChild < leftChild!)) swap = rightChildIdx;
      }
      if (swap === null) break;
      this.heap[idx] = this.heap[swap];
      this.heap[swap] = element;
      idx = swap;
    }
  }
}

const pq = new MinPriorityQueue();
pq.extractMin();
console.log(pq.heap);

A [3, 5, 8]

B [5, 3, 8]

C [8, 3, 5]

D [3, 8, 5]

💡 Hint

After removing the root, replace it with the last element and sink it down to restore heap property.

Remove 1, replace root with 5 → [5,3,8]. Sink down swaps 5 with 3 → [3,5,8].

🧠 Conceptual

advanced

Which statement about Priority Queues is true?

Select the correct statement about priority queues.

A Priority queues can only be implemented using arrays without any additional structure.

B Priority queues do not support changing the priority of an element once inserted.

C Priority queues allow insertion and extraction of the highest priority element efficiently.

D Priority queues always maintain elements in sorted order internally.

💡 Hint

Think about what operations priority queues optimize.

Priority queues efficiently insert elements and extract the highest priority element (min or max) but do not keep all elements fully sorted internally.

🔧 Debug

advanced

Identify the error in this Priority Queue sinkDown method

What error will occur when running this sinkDown method in a min-priority queue?

DSA Typescript

sinkDown() {
  let idx = 0;
  const length = this.heap.length;
  const element = this.heap[0];
  while (true) {
    let leftChildIdx = 2 * idx + 1;
    let rightChildIdx = 2 * idx + 2;
    let leftChild, rightChild;
    let swap = null;

    if (leftChildIdx < length) {
      leftChild = this.heap[leftChildIdx];
      if (leftChild < element) swap = leftChildIdx;
    }
    if (rightChildIdx < length) {
      rightChild = this.heap[rightChildIdx];
      if ((swap === null && rightChild < element) || (swap !== null && rightChild < leftChild!)) swap = rightChildIdx;
    }
    if (swap === null) break;
    this.heap[idx] = this.heap[swap];
    this.heap[swap] = element;
    idx = swap;
  }
}

A No error; method works correctly

B TypeError because leftChild might be undefined when compared

C ReferenceError due to missing variable declaration

D Logical error causing infinite loop

💡 Hint

Check the condition where rightChild is compared to leftChild without ensuring leftChild is defined.

If leftChildIdx is out of range, leftChild is undefined. Comparing rightChild < leftChild causes TypeError.

🚀 Application

expert

How many elements are in the priority queue after these operations?

Start with an empty max-priority queue. Perform these operations in order: insert(10), insert(20), extractMax(), insert(15), extractMax(), insert(5). How many elements remain in the queue?

DSA Typescript

class MaxPriorityQueue {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    const element = this.heap[idx];
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.heap[parentIdx];
      if (element <= parent) break;
      this.heap[parentIdx] = element;
      this.heap[idx] = parent;
      idx = parentIdx;
    }
  }

  extractMax() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return max;
  }

  sinkDown() {
    let idx = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (leftChild > element) swap = leftChildIdx;
      }
      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild!)) swap = rightChildIdx;
      }
      if (swap === null) break;
      this.heap[idx] = this.heap[swap];
      this.heap[swap] = element;
      idx = swap;
    }
  }
}

const pq = new MaxPriorityQueue();
pq.insert(10);
pq.insert(20);
pq.extractMax();
pq.insert(15);
pq.extractMax();
pq.insert(5);
console.log(pq.heap.length);

A 2

B 1

C 3

D 4

💡 Hint

Count insertions and extractions carefully step-by-step.

Insert 10 (1 element), insert 20 (2 elements), extractMax removes 20 (1 element), insert 15 (2 elements), extractMax removes 15 (1 element), insert 5 (2 elements). Final count is 2.

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