Task Scheduler - Algorithm and Data Structure Project [in JavaScript]

In this article at OpenGenus, we are going to build a task scheduler project which implements a priority queue, and we will use a min heap data structure to manage the tasks based on their priorities.

Table of Contents

1. What is a task scheduler?

2. Task Scheduler methods

   • addTask()
   • getNextTask()
   • deleteTask()

3. The heapify algorithm

   • heapifyUp()
   • heapifyDown()

4. Analysis

1. What is a task scheduler?

A task scheduler is a tool where the user adds tasks with the task name, the task priority, and the expected duration of the task. Then, the scheduler will organize the tasks based on their final priority which is calculated from the priority and the expected duration. So basically the task with the lowest final priority will be on top of the list (for example, if Task 1's final priority is 2 and Task 2's final priority is 1, then Task 2 will be on top of Task1). The user can also delete a task or get the next task in the list.

2. Task Scheduler methods

• addTask()
  First, let's create a class called TaskScheduler which will be a blueprint for creating objects with shared methods and properties:

class TaskScheduler {
  constructor() {
    this.tasks = [];
  }
 }
 
 const scheduler = new TaskScheduler(); // {tasks: []}

The constructor method is automatically called when an object of the class is created. It initializes the object's properties, setting up the initial state. In this case, we have one property called tasks which is assigned an empty array that will hold the tasks.
After the class, we create an instance of the class by using the new keyword and we store it in the scheduler variable.
Now, let's create the addTask() method.

 addTask(task, priority, expectedDuration) {
    const finalPriority = Math.round(priority / expectedDuration);
    this.tasks.push({ task, priority, expectedDuration, finalPriority });
    this.heapifyUp(this.tasks.length - 1);
  }

When we add a task, we will include the task's name, the priority of the task, and the expected duration (in minutes) of the task. Then, we will calculate the task's final priority by dividing the expected duration from the priority and round the number. After that, we add the new task in the tasks array and we will use a heapify algorithm (I will explain this later in the article) to arrange the tasks in their final priority order.

scheduler.addTask("Task 3", 1, 2);
scheduler.addTask("Task 1", 2, 1);
scheduler.addTask("Task 2", 3, 3);

This is how our task scheduler looks like:

TaskScheduler {
  tasks: [
    {
      task: 'Task 3',
      priority: 1,
      expectedDuration: 2,
      finalPriority: 1
    },
    {
      task: 'Task 1',
      priority: 2,
      expectedDuration: 1,
      finalPriority: 2
    },
    {
      task: 'Task 2',
      priority: 3,
      expectedDuration: 3,
      finalPriority: 1
    }
  ]
}

• getNextTask()

 getNextTask() {
    if (this.tasks.length === 0) {
      return null;
    }

    const nextTask = this.tasks[0];
    
    if (this.tasks.length > 1) {
      this.tasks[0] = this.tasks.pop();
      this.heapifyDown(0);
    } else {
      this.tasks.pop();
    }
    return nextTask.task;
  }

If there are no tasks then we will return null.
If there are tasks then we will get the first task and store it in the nextTask variable. When we first call the getNextTask() method, the first task will be returned. If there are more than 1 tasks in the list then we replace the first task with the last task and the heapifyDown() method will be responsible for maintaining the tasks order and priority. So the next time we call getNextTask() method, the second task will be returned and so on. But if there's only 1 task in the list, then we will return null, as there's no more tasks after the first one. This method is basically retrieveing and removing the highest priority task from the tasks array while maintaining the remaining tasks order and priority.

scheduler.getNextTask(); // Task 3
scheduler.getNextTask(); // Task 2
scheduler.getNextTask(); // Task 1

If two tasks have the same final priority, then the task which was added first in the list will be placed first (Task 3 and Task 2 have the same final priority 1).

• deleteTask()

deleteTask(task) {
    const index = this.tasks.findIndex((t) => t.task === task);

    if (index !== -1) {
      this.tasks.splice(index, 1);
    } else {
      return;
    }
  }

When we want to delete a task, first we will find its index by using the findIndex() method. If we have an index (if the index is not -1), then we will remove the task from the list using the splice() method, otherwise, we will just return and do nothing.

scheduler.deleteTask("Task 1");

TaskScheduler {
  tasks: [
    {
      task: 'Task 3',
      priority: 1,
      expectedDuration: 2,
      finalPriority: 1
    },
    {
      task: 'Task 2',
      priority: 3,
      expectedDuration: 3,
      finalPriority: 1
    }
  ]
}

3. The heapify algorithm

Now, let's see how the heapify methods work.

• heapifyUp()

heapifyUp(index) {
    const currentTask = this.tasks[index];
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parentTask = this.tasks[parentIndex];
     
      if (this.compareTasks(currentTask, parentTask) >= 0) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  
compareTasks(task1, task2) {
    return task1.finalPriority - task2.finalPriority;
  }

swap(x, y) {
    [this.tasks[x], this.tasks[y]] = [this.tasks[y], this.tasks[x]];
  }

We use this method when we add a new task.
First, we will get the current task (the new task we just added to the list) and store it in the currentTask variable. After that, we will use a while loop to arrange the tasks based on their priority.
Inside the loop, we will get the parent task (which is above the current task) and then we will compare the two tasks using the compareTasks() method. If the final priority is greater than or equal 0, then we will break out of the loop, otherwise, we will swap the two tasks using the swap() method to change their orders. The loop will go on until the condition (index > 0) will become falsy.

• heapifyDown()

 heapifyDown(index) {
    const currentTask = this.tasks[index];
    const length = this.tasks.length;
    
    while (true) {
      let childIndex = null;
      let minPriority = currentTask.finalPriority;

      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if (leftChildIndex < length) {
        const leftChild = this.tasks[leftChildIndex];

        if (this.compareTasks(leftChild, currentTask) < 0) {
          childIndex = leftChildIndex;
          minPriority = leftChild.finalPriority;
        }
      }

      if (rightChildIndex < length) {
        const rightChild = this.tasks[rightChildIndex];

        if (this.compareTasks(rightChild, currentTask) < 0) {
          childIndex = rightChildIndex;
          minPriority = rightChild.finalPriority;
        }
      }

      if (childIndex === null) {
        break;
      }

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

This method will be used when we use the getNextTask() method which removes the first task from the list.
Again, we will get the current task and also the length of the list, then we store them in their appropriate variables. Then, we will start an infinite loop that will break when the task reaches its correct position.
We assign the childIndex to be null in the beginning and the minPriority to be the current task's final priority. Then, we will get the index of the left and right child of the current task.
After assigning these values to the variables, we will check if the left and right child exist.

 if (leftChildIndex < length) {
        const leftChild = this.tasks[leftChildIndex];

        if (this.compareTasks(leftChild, currentTask) < 0) {
          childIndex = leftChildIndex;
          minPriority = leftChild.finalPriority;
        }
      }

If the left child exist, then we will compare it with the current task using the compareTasks() method. If the left child has lower priority, then we will assign the childIndex to be index of the left child and the minPriority to be the final priority of the left child.
Then we move on to check the right child.

if (rightChildIndex < length) {
        const rightChild = this.tasks[rightChildIndex];

        if (this.compareTasks(rightChild, currentTask) < 0) {
          childIndex = rightChildIndex;
          minPriority = rightChild.finalPriority;
        }
      }

If the rigth child exist, then we will compare it with the current task. If the right child has lower priority, then we will assign the childIndex to be index of the right child and the minPriority to be the final priority of the right child.
If the childIndex becomes null, then we will break out of the loop.
If it's not null, then we will swap the two tasks at index and childIndex to push down the current task to its correct position.
So by repeatedly swapping the task with its lower priority child, the task goes down to its correct position, ensuring that the task with the highest priority stays at the top.

4. Analysis

Lets analyze the efficiency of the algorithms we used.

• Time Complexity:
  This is the amount of time an algorithm takes to run in relation to the size of the input. It measures how the runtime increases of the algorithm as the size of the input increases. For the time complexity we use the Big O notation, O(). This provides an upper bound on the growth rate of the algorithm.

  • compareTasks(): This method doesn't depend on the size of the tasks and it performs constant-time operations, O(1). The algorithm takes the same amount of time, regardless the size of the input.

  • deleteTask(): The method uses findIndex() and splice() which have linear time complexity, O(n). The runtime grows linearly with the input size.

  • addTask(), getNextTask(), heapifyUp(), heapifyDown(): All these methods have logarithmic time, so the runtime grows logarithmically with the input size, O(log n).

• Space Complexity:
  This is the amount of memory or space an algorithm requires to run in relation to the size of the input. It measures how much additional memory it uses as the input grows. We also use the Big O notation here as well.

  • All methods: All of the methods use the O(1) constant space because they use a fixed amount of memory, regardless of the input size.

• Possible other algorithmic approaches:

  • Linked list sorted by priority: Here we could use a linked list to store the tasks and sorted by priority.

  • Priority queue with binary heap: Instead of using an array as in the current implementation, we can maintain the heap property using a binary heap data structure.

Here is a table comparison of the 3 approaches:

Methods	Min Heap	Linked List	Priority Queue
addTask()	O(log n)	O(n)	O(log n)
deleteTask()	O(n)	O(1)	O(n)
getNextTask()	O(log n)	O(1)	O(1)
compareTasks()	O(1)	O(1)	O(1)
swap()	O(1)	O(1)	O(1)

You can checkout the full code here: https://github.com/OpenGenus/task-scheduler