Implementing a Task Heap Service in TypeScript

A task heap is a data structure commonly used in computer science to efficiently manage tasks based on their execution time. In this article, we'll delve into the implementation of a Task Heap Service in TypeScript. This service allows us to insert tasks, extract the task with the shortest execution time, and perform other operations efficiently.

interface Task {
  executionTime: number;
  data: any;
}

class TaskHeapService {
  private heap: Task[] = [];
  constructor() {
    this.heap = [];
  }

  insert(task: Task) {
    this.heap.push(task);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp = (index: number) => {
    if (index <= 0) {
      return;
    }

    const parentIndex = Math.floor((index - 1) / 2);

    if (this.heap[parentIndex].executionTime > this.heap[index].executionTime) {]
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      this.bubbleUp(parentIndex);
    }
  };

  bubbleDown = (index: number) => {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let smallestIndex = index;

    if (
      leftChildIndex < this.heap.length &&
      this.heap[leftChildIndex].executionTime <
        this.heap[smallestIndex].executionTime
    ) {
      smallestIndex = leftChildIndex;
    }

    if (
      rightChildIndex < this.heap.length &&
      this.heap[rightChildIndex].executionTime <
        this.heap[smallestIndex].executionTime
    ) {
      smallestIndex = rightChildIndex;
    }

    if (smallestIndex !== index) {
      [this.heap[smallestIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[smallestIndex],
      ];
      this.bubbleDown(smallestIndex);
    }
  };

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }

    if (this.heap.length === 1) {
      return this.heap.pop();
    }

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  getLength() {
    return this.heap.length;
  }

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

  peek() {
    return this.heap[0];
  }
}

export default TaskHeapService;

And then you can use it like

const taskHeap = new TaskHeapService();

taskHeap.insert({ executionTime: 10, data: "Task A" });
taskHeap.insert({ executionTime: 5, data: "Task B" });
taskHeap.insert({ executionTime: 15, data: "Task C" });

console.log(taskHeap.extractMin()); // { executionTime: 5, data: "Task B" }
console.log(taskHeap.peek()); // { executionTime: 10, data: "Task A" }

The Task Heap Service implemented in this article provides an efficient way to manage tasks based on their execution time. By maintaining the heap property during insertions and extractions, it ensures that the task with the shortest execution time is always readily available. Understanding and implementing such data structures is essential for building scalable and performant applications.