Implementing Priority Queues with Heaps in JavaScript

7.3.2 Implementing Priority Queues with Heaps

In this section, we delve into the implementation of priority queues using heaps in JavaScript. Priority queues are an essential data structure in computer science, providing a way to manage elements with associated priorities efficiently. By the end of this section, you will have a comprehensive understanding of how to implement a priority queue using a heap, handle elements with priorities, and perform essential operations.

Understanding Priority Queues

A priority queue is a data structure where each element has a priority associated with it. Elements with higher priority are served before elements with lower priority. This is different from a standard queue, which operates on a first-in-first-out (FIFO) basis. Priority queues are widely used in scenarios such as scheduling tasks, managing resources, and implementing algorithms like Dijkstra’s shortest path.

Why Use Heaps for Priority Queues?

Heaps are an ideal choice for implementing priority queues because they allow efficient retrieval of the highest (or lowest) priority element. A binary heap, specifically, provides O(log n) time complexity for insertion and deletion operations, making it suitable for dynamic priority queue operations.

Implementing Priority Queue with a Min-Heap

In a min-heap, the element with the lowest priority value (highest priority) is always at the root. Let’s define a PriorityQueue class using a min-heap in JavaScript.

Defining the PriorityQueue Class

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

  enqueue(element, priority) {
    const node = new Node(element, priority);
    this.heap.push(node);
    this.bubbleUp();
  }

  dequeue() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop().element;
    const topNode = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return topNode.element;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = this.getParentIndex(index);
      if (this.heap[index].priority >= this.heap[parentIndex].priority) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftChildIndex = this.getLeftChildIndex(index);
      let rightChildIndex = this.getRightChildIndex(index);
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild.priority < element.priority) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild.priority < element.priority) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }
}

class Node {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

Key Methods Explained

• enqueue(element, priority): Adds a new element to the priority queue with an associated priority. The element is inserted at the end of the heap, and the bubbleUp method is called to maintain the heap property.

• dequeue(): Removes and returns the element with the highest priority (lowest priority value). The root element is replaced with the last element in the heap, and the bubbleDown method is called to restore the heap structure.

• bubbleUp(): Ensures that the newly added element moves up the heap until the heap property is satisfied. It compares the element with its parent and swaps them if necessary.

• bubbleDown(): Ensures that the root element moves down the heap to maintain the heap property after a removal. It compares the element with its children and swaps it with the smaller child if needed.

Practical Example

Let’s see how this priority queue can be used in practice:

const pq = new PriorityQueue();
pq.enqueue('Task 1', 2);
pq.enqueue('Task 2', 1);
pq.enqueue('Task 3', 3);

console.log(pq.dequeue()); // Output: 'Task 2'
console.log(pq.dequeue()); // Output: 'Task 1'
console.log(pq.dequeue()); // Output: 'Task 3'

In this example, tasks are enqueued with different priorities. The task with the highest priority (lowest priority number) is dequeued first.

Handling Edge Cases

• Empty Queue: The dequeue method returns null if the queue is empty, preventing errors when attempting to remove an element from an empty queue.

• Single Element Queue: If the queue contains only one element, dequeue simply removes and returns that element without needing to adjust the heap.

Optimizations and Best Practices

• Heap Size Management: Consider implementing dynamic resizing for the heap array to handle large numbers of elements efficiently.

• Priority Comparison: Ensure that the priority comparison logic is consistent and correctly implemented in both bubbleUp and bubbleDown methods.

• Memory Usage: Be mindful of memory usage, especially when dealing with large datasets. Implementing a garbage collection mechanism or using a more memory-efficient data structure might be necessary for specific applications.

Visualizing the Heap Structure

To better understand the heap structure, let’s visualize the heap operations using a diagram. Here’s a simple representation of the heap after several enqueue operations:

    graph TD;
	    A[Root: Task 2 (Priority 1)]
	    B[Task 1 (Priority 2)]
	    C[Task 3 (Priority 3)]
	    A --> B;
	    A --> C;

This diagram shows the heap structure with Task 2 as the root, having the highest priority.

Conclusion

Implementing a priority queue using a heap in JavaScript provides an efficient way to manage elements with priorities. By leveraging the properties of a binary heap, we can perform insertion and deletion operations in logarithmic time, making this data structure suitable for various applications, including task scheduling and resource management.

Further Reading and Resources

• JavaScript Data Structures and Algorithms
• Heap Data Structure
• Priority Queue Applications

Quiz Time!