Priority Queue Introduction and Concept in DSA Javascript

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:
[5] -> [4] -> [3] -> [1] -> null
↑ front (highest priority)

Dry Run Walkthrough

Input: Insert values 3, 5, 1, 4 into an empty priority queue where higher numbers have higher priority.

Goal: To keep the queue ordered so the highest number is always at the front.

Step 1: Insert 3 into empty queue

[3] -> null

Why: Start with the first element as the only item in the queue

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

[5] -> [3] -> null

Why: 5 goes before 3 because it has higher priority

Step 3: Insert 1, which is lower priority than 3

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

Why: 1 goes to the end because it has the lowest priority

Step 4: Insert 4, which fits between 5 and 3

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

Why: 4 is placed after 5 but before 3 to keep order

Result:

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

Annotated Code

DSA Javascript

class Node {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
    this.next = null;
  }
}

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

  enqueue(value, priority) {
    const newNode = new Node(value, priority);
    if (!this.front || priority > this.front.priority) {
      newNode.next = this.front;
      this.front = newNode;
      return;
    }
    let current = this.front;
    while (current.next && current.next.priority >= priority) {
      current = current.next;
    }
    newNode.next = current.next;
    current.next = newNode;
  }

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

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

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

Insert new node at front if queue is empty or new node has higher priority than front

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

Traverse queue to find correct position where next node has lower priority

newNode.next = current.next; current.next = newNode;

Insert new node in its correct position to maintain priority order

Output

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

Complexity Analysis

Time: O(n) because in worst case we may need to traverse all nodes to insert in correct position

Space: O(n) because we store all elements in linked nodes

vs Alternative: Compared to a simple queue where insertion is O(1), priority queue insertion is slower but keeps order for quick access to highest priority

Edge Cases

Empty queue

New node becomes the front node

DSA Javascript

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

New node has highest priority

New node is inserted at the front

DSA Javascript

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

New node has lowest priority

New node is inserted at the end

DSA Javascript

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

When to Use This Pattern

When you need to process items by importance rather than arrival order, reach for the priority queue pattern because it keeps the highest priority item ready to use.

Common Mistakes

Mistake: Inserting new nodes without checking priority order, causing the queue to lose priority sorting
Fix: Always traverse to find the correct position based on priority before inserting

Mistake: Not handling empty queue case, causing errors on first insert
Fix: Check if the queue is empty and insert the first node as front

Summary

A priority queue stores elements so that the highest priority is always at the front.

Use it when you want to process items by importance, not just arrival order.

The key is to insert each new item in the right place to keep the queue sorted by priority.

Practice

1. What is the main difference between a Priority Queue and a regular queue?

easy

A. Elements are always dequeued in the order they were enqueued

B. Elements are dequeued based on priority, not just order of arrival

C. It only stores numbers, not other data types

D. It uses a stack internally to manage elements

Solution

1. Step 1: Understand queue behavior

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

2. Step 2: Understand priority queue behavior

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

3. Final Answer:

   Elements are dequeued based on priority, not just order of arrival -> Option B

4. Quick Check:

   Priority Queue = priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Thinking priority queue works like a normal queue
• Assuming priority queue only stores numbers
• Confusing priority queue with stack

2. Which of the following is the correct way to declare a priority queue class in JavaScript?

easy

A. let PriorityQueue = () => { this.items = []; }

B. function PriorityQueue() { this.items = {}; }

C. class PriorityQueue { constructor() { this.items = []; } }

D. var PriorityQueue = new Array();

Solution

1. Step 1: Check class syntax

   class PriorityQueue { constructor() { this.items = []; } } uses correct ES6 class syntax with constructor initializing an array.

2. Step 2: Check other options

   function PriorityQueue() { this.items = {}; } uses function but initializes an object, not array; let PriorityQueue = () => { this.items = []; } uses arrow function incorrectly for class; var PriorityQueue = new Array(); assigns array directly, not a class.

3. Final Answer:

   class PriorityQueue { constructor() { this.items = []; } } -> Option C

4. Quick Check:

   Correct class syntax = class PriorityQueue { constructor() { this.items = []; } } [OK]

Hint: Use ES6 class with constructor for priority queue [OK]

Common Mistakes:

• Using arrow functions as classes
• Initializing items as object instead of array
• Assigning array directly without class

3. Consider this JavaScript code using a simple priority queue implementation:

class PriorityQueue {
  constructor() {
    this.items = [];
  }
  enqueue(element, priority) {
    this.items.push({element, priority});
    this.items.sort((a, b) => a.priority - b.priority);
  }
  dequeue() {
    return this.items.shift().element;
  }
}

const pq = new PriorityQueue();
pq.enqueue('A', 2);
pq.enqueue('B', 1);
pq.enqueue('C', 3);
console.log(pq.dequeue());

What will be printed?

medium

A. 'B'

B. 'A'

C. 'C'

D. undefined

Solution

1. Step 1: Analyze enqueue operations

   Elements are added with priorities: A(2), B(1), C(3). After each enqueue, array is sorted by priority ascending.

2. Step 2: Analyze dequeue operation

   Dequeue removes first element (lowest priority number). After sorting, order is B(1), A(2), C(3). So dequeue returns 'B'.

3. Final Answer:

   'B' -> Option A

4. Quick Check:

   Lowest priority dequeued first = 'B' [OK]

Hint: Lowest priority number dequeued first [OK]

Common Mistakes:

• Assuming FIFO order instead of priority
• Confusing priority sorting order
• Forgetting to return element, not object

4. The following code is intended to implement a priority queue, but it has a bug:

class PriorityQueue {
  constructor() {
    this.items = [];
  }
  enqueue(element, priority) {
    this.items.push({element, priority});
  }
  dequeue() {
    return this.items.shift().element;
  }
}

What is the main problem with this code?

medium

A. It stores elements as objects instead of arrays

B. It uses shift() instead of pop() to remove elements

C. It does not initialize items array in constructor

D. It does not sort items by priority before dequeue

Solution

1. Step 1: Check enqueue method

   Enqueue adds elements but does not sort by priority.

2. Step 2: Check dequeue method

   Dequeue removes first element, but without sorting, priority order is not guaranteed.

3. Final Answer:

   It does not sort items by priority before dequeue -> Option D

4. Quick Check:

   Missing sorting causes wrong dequeue order [OK]

Hint: Sort items by priority before dequeue [OK]

Common Mistakes:

• Assuming shift() removes highest priority
• Ignoring sorting requirement
• Confusing object vs array storage

5. You want to implement a priority queue that supports fast insertion and removal of the highest priority element. Which data structure is best suited for this, and why?

hard

A. Binary heap, because it provides efficient insert and remove operations

B. Linked list, because it maintains insertion order

C. Stack, because it removes the last inserted element quickly

D. Array, because it allows easy sorting after each insertion

Solution

1. Step 1: Understand operation needs

   Priority queue needs fast insertion and removal of highest priority element.

2. Step 2: Compare data structures

   Array requires sorting after insertion (slow). Linked list maintains order but slow for priority. Stack removes last inserted only. Binary heap supports insert and remove in O(log n) time efficiently.

3. Final Answer:

   Binary heap, because it provides efficient insert and remove operations -> Option A

4. Quick Check:

   Binary heap = efficient priority queue [OK]

Hint: Use binary heap for efficient priority queue operations [OK]

Common Mistakes:

• Choosing array and ignoring sorting cost
• Confusing stack with priority queue
• Ignoring time complexity of operations