Implementing a Priority Queue in TypeScript: A Step-by-Step Guide

Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.

Introduction

A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.

Why TypeScript?

TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.

Step 1: Define the Priority Queue Class

First, let’s create a PriorityQueue class that will hold our heap.

class PriorityQueue<T> {
  private heap: T[] = [];

  constructor(private comparator: (a: T, b: T) => number) {}
}

• heap: An array representing the binary heap.
• comparator: A function to compare two elements, defining the priority.

Step 2: Implement the Helper Methods

Swap Method

We need a method to swap two elements in the heap.

private swap(i: number, j: number): void {
  [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}

Parent and Child Index Methods

Calculate the indices of parent and child nodes.

private parentIndex(index: number): number {
  return Math.floor((index - 1) / 2);
}

private leftChildIndex(index: number): number {
  return 2 * index + 1;
}

private rightChildIndex(index: number): number {
  return 2 * index + 2;
}

Step 3: Implement the Push Method

Add a new element to the heap and reorder it to maintain the heap property.

push(item: T): void {
  this.heap.push(item);
  this.heapifyUp();
}

Heapify Up

Move the new element up to its correct position.

private heapifyUp(): void {
  let index = this.heap.length - 1;
  while (
    index > 0 &&
    this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
  ) {
    this.swap(index, this.parentIndex(index));
    index = this.parentIndex(index);
  }
}

Step 4: Implement the Pop Method

Remove and return the element with the highest priority.

pop(): T | undefined {
  if (this.heap.length === 0) return undefined;
  if (this.heap.length === 1) return this.heap.pop();

  const item = this.heap[0];
  this.heap[0] = this.heap.pop() as T;
  this.heapifyDown();
  return item;
}

Heapify Down

Reorder the heap after removing the root element.

private heapifyDown(): void {
  let index = 0;
  const length = this.heap.length;

  while (this.leftChildIndex(index) < length) {
    let smallestChildIndex = this.leftChildIndex(index);
    const rightChildIdx = this.rightChildIndex(index);

    if (
      rightChildIdx < length &&
      this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
    ) {
      smallestChildIndex = rightChildIdx;
    }

    if (
      this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
    ) {
      break;
    }

    this.swap(index, smallestChildIndex);
    index = smallestChildIndex;
  }
}

Step 5: Implement Peek and Size Methods

Get the element with the highest priority without removing it and get the size of the queue.

peek(): T | undefined {
  return this.heap[0];
}

size(): number {
  return this.heap.length;
}

Step 6: Implement the Update Method

Now, we’ll implement an update() method that allows us to update the priority of an element, either by its index or by its value.

Update by Index

updateAt(index: number, newValue: T): void {
  if (index < 0 || index >= this.heap.length) {
    throw new Error("Index out of bounds");
  }

  const oldValue = this.heap[index];
  this.heap[index] = newValue;

  if (this.comparator(newValue, oldValue) < 0) {
    this.heapifyUp(index);
  } else {
    this.heapifyDown(index);
  }
}

Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.

Update by Value

Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.

update(value: T, newValue: T): void {
  const index = this.heap.findIndex((element) => element === value);
  if (index === -1) {
    throw new Error("Value not found in heap");
  }
  this.updateAt(index, newValue);
}

Explanation: We find the index of the value in the heap and then call updateAt() to update it.

Remove and Remove By Index

  public remove(item: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.removeAtIndex(index);
  }

  private removeAtIndex(index: number): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    if (index === this.heap.length - 1) {
      this.heap.pop();
    } else {
      this.heap[index] = this.heap.pop() as T;
      const parentIndex = this.parent(index);
      if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        this.heapifyUp(index);
      } else {
        this.heapifyDown(index);
      }
    }
  }

Step 7: Implement the Heapify Function

We’ll add a heapify() method to build a heap from an existing array.

heapify(array: T[]): void {
  this.heap = array;
  for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
    this.heapifyDown(i);
  }
}

Step 8: Use the Priority Queue to Solve LeetCode 215

Now, let’s use our PriorityQueue to find the Kth largest element in an array.

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Solution

We’ll use a min-heap (priority queue) to keep track of the largest k elements.

function findKthLargest(nums: number[], k: number): number {
  const pq = new PriorityQueue<number>((a, b) => a - b);

  for (const num of nums) {
    pq.push(num);
    if (pq.size() > k) {
      pq.pop();
    }
  }

  return pq.peek() as number;
}

Comparator: (a, b) => a - b ensures a min-heap.

Logic: Maintain a heap of size k. The root will be the kth largest element.

Full Code Listing with small changes in variable names

class PriorityQueue<T> {
  private heap: T[];

  constructor(private compare: (a: T, b: T) => number) {
    this.heap = [];
  }

  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  private parent(i: number): number {
    return Math.floor((i - 1) / 2);
  }

  private left(i: number): number {
    return 2 * i + 1;
  }

  private right(i: number): number {
    return 2 * i + 2;
  }

  private heapifyUp(index: number): void {
   while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
    this.swap(index, this.parent(index));
      index = this.parent(index);
    }
  }

  private heapifyDown(index: number): void {
    const length = this.heap.length;

    while (this.left(index) < length) {
      let smallest = this.left(index);
      const rightIndex = this.right(index);
      if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
        smallest = rightIndex;
      }
      if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  public push(item: T): void {
    this.heap.push(item);
    this.heapifyUp(this.heap.length - 1);
  }

  public pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop() as T;
    this.heapifyDown(0);
    return root;
  }

  public peek(): T | undefined {
    return this.heap[0];
  }

  public size(): number {
    return this.heap.length;
  }

  public updateAtIndex(index: number, newItem: T): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    this.heap[index] = newItem;
    if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
      this.heapifyUp(index);
    } else {
      this.heapifyDown(index);
    }
  }

  public update(item: T, newItem: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.updateAtIndex(index, newItem);
  }

  public remove(item: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.removeAtIndex(index);
  }

  private removeAtIndex(index: number): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    if (index === this.heap.length - 1) {
      this.heap.pop();
    } else {
      this.heap[index] = this.heap.pop() as T;
      const parentIndex = this.parent(index);
      if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        this.heapifyUp(index);
      } else {
        this.heapifyDown(index);
      }
    }
  }

  public isEmpty(): boolean {
    return this.heap.length === 0;
  }

  public heapify(array: T[]): void {
    this.heap = array;
    for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
      this.heapifyDown(i);
    }
  }
}

Testing the Solution

Let’s test our implementation with an example.

const nums = [3, 2, 1, 5, 6, 4];
const k = 2;

const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5

Testing the Update and Heapify Methods

Using heapify() to Build a Heap from an Array

typescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);

console.log(pq.peek()); // Output: 1

Rewriting the findKthLargest Function Using heapify()

We can optimize our earlier findKthLargest function by using heapify().

function findKthLargest(nums: number[], k: number): number {
  const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap

  pq.heapify(nums);

  for (let i = 0; i < k - 1; i++) {
    pq.pop();
  }

  return pq.peek() as number;
}

Why Use heapifyDown() in heapify()?

That’s a great question! In the heapify() method, we use heapifyDown() instead of heapifyUp() because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.

When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown() on each node. This process is known as the heapify algorithm or build heap.

Reasons:

1. Higher Efficiency:
   • Lower Time Complexity: Using heapifyDown(), the overall time complexity of building the heap is O(n). If we were to use heapifyUp(), the time complexity would increase to O(n log n) in the worst case.
   • Fewer Node Movements: heapifyDown() can fix all violations of the heap property from the current node down to the leaves in one pass, whereas heapifyUp() might require multiple passes for each node.
2. Suitable for Building the Entire Heap:
   • heapifyDown() is more appropriate when you need to adjust the heap starting from the internal nodes downwards.
   • heapifyUp() is typically used when inserting a new element into an already built heap.

Detailed Explanation

When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.

heapify(array: T[]): void {
  this.heap = array;
  for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
    this.heapifyDown(i);
  }
}

• Calculating the Starting Index: Math.floor(this.heap.length / 2) - 1
  • This formula gives us the index of the last non-leaf node.
  • In a binary heap, nodes with indices from Math.floor(n/2) to n - 1 are all leaf nodes.
• Why Not Use heapifyUp()?
  • heapifyUp() is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.
  • Using heapifyUp() during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels.
  • In contrast, heapifyDown() can adjust the subtree rooted at a node in one pass.

An Example

Suppose we have an array [3, 2, 1, 5, 6, 4] and we want to build a min-heap.

1. Initialize the Heap:typescriptCopy codethis.heap = [3, 2, 1, 5, 6, 4];
2. Start from the Last Non-Leaf Node:
   • The array length is 6, so the index of the last non-leaf node is Math.floor(6 / 2) - 1 = 2.
3. Perform heapifyDown() on Index 2:
   • The node at index 2 has a value 1, and its children are out of bounds, so no action is needed.
4. Perform heapifyDown() on Index 1:
   • The node at index 1 has a value 2, with left child 5 and right child 6.
   • Since 2 is less than its children, no action is needed.
5. Perform heapifyDown() on Index 0:
   • The node at index 0 has a value 3, with left child 2 and right child 1.The right child 1 is the smallest, so we swap 3 with 1.
   • The heap now looks like [1, 2, 3, 5, 6, 4].
6. Continue heapifyDown() on the Swapped Node:
   • The node at index 2 (now with value 3) has a left child 4, but since 3 is less than 4, no further action is needed.

Summary

• Using heapifyDown():
  • Ideal for building a heap from an array.
  • Overall time complexity is O(n).
• Using heapifyUp():
  • Suitable for inserting a single element into an existing heap.
  • Each insertion has a time complexity of O(log n).

Therefore, in the heapify() method, we choose heapifyDown() to efficiently build a valid heap from the bottom up.

Additional Notes

• Why Not Use heapifyUp()?
  • If we used heapifyUp() on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity.
  • heapifyDown() allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.
• Time Complexity Comparison:
  • Using heapifyDown(): Total time complexity is O(n).
  • Using heapifyUp(): Total time complexity is O(n log n).

Conclusion

We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.

References

• TypeScript Official Website
• Heap Data Structure
• LeetCode Problem 215