×

Search anything:

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

#### Algorithms Data Structures Get this book -> Problems on Array: For Interviews and Competitive Programming

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.

1. What is a task scheduler?

3. The heapify algorithm

• heapifyUp()
• heapifyDown()
4. Analysis

## 1. What is a task scheduler?

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

``````

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.

`````` addTask(task, priority, expectedDuration) {
const finalPriority = Math.round(priority / expectedDuration);
}
``````

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);
``````

This is how our task scheduler looks like:

``````TaskScheduler {
{
priority: 1,
expectedDuration: 2,
finalPriority: 1
},
{
priority: 2,
expectedDuration: 1,
finalPriority: 2
},
{
priority: 3,
expectedDuration: 3,
finalPriority: 1
}
]
}
``````
`````` getNextTask() {
return null;
}

this.heapifyDown(0);
} else {
}
}
``````

If there are no tasks then we will return null.

``````scheduler.getNextTask(); // Task 3
``````

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(task) {

if (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");

{
priority: 1,
expectedDuration: 2,
finalPriority: 1
},
{
priority: 3,
expectedDuration: 3,
finalPriority: 1
}
]
}
``````

## 3. The heapify algorithm

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

• heapifyUp()
``````heapifyUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);

break;
}
this.swap(index, parentIndex);
index = parentIndex;
}
}

}

swap(x, y) {
}
``````

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) {

while (true) {
let childIndex = null;

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

if (leftChildIndex < length) {

childIndex = leftChildIndex;
minPriority = leftChild.finalPriority;
}
}

if (rightChildIndex < length) {

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) {

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) {

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
swap() O(1) O(1) O(1)

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