⚙️ Leetcode Heap (Priority Queue) in JavaScript
Tags: javascript, algorithms, tutorial, heap
Published: 2023-11-20 17:04:10

## Introduction
Hey there, fellow JavaScript devs! If you're here, chances are you're diving into the heap of questions on LeetCode – been there, done that. I get it. I used to wrestle with those same challenges, and now I want to be the friend who helps you through the struggle. So, if you're scratching your head over heap problems, relax, I've got your back. JavaScript doesn't have any Priority Queue built-in function. You need to understand these important codes to solve heap questions in LeetCode with JavaScript.


## JavaScript in Leetcode

According to the LeetCode support page, they utilize [@datastructures-js/priority-queue](https://github.com/datastructures-js/priority-queue/tree/master) package. It mentioned that the version is **v4.1**. However, after exploring the package, I realized we could also use the **v5**. Therefore, if you want to go to the official documentation in Github, you need to make sure that you are looking at **v5**. I believe **v5** is the complement of **v4**, so you just need to check the **v5** docs.

![docs](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9whd275nvldxw4pjmunb.png)

## Heap (Priority Queue) in General

I will not discuss how the heap works in depth because that's not the purpose of this blog. The main idea of a heap is it will keep maintaining the order of all the data. If you are using the **Minimum Priority Queue**, the first element will be the smallest. Therefore, it's the same idea for the **Maximum Priority Queue**

Take a look at the Min Heap simulation here.
![Visualiation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h7uwu8miwpuwowomodag.gif)

Visualization Link:
https://www.cs.usfca.edu/~galles/visualization/Heap.html

## 🔵 Initialization
There are three constructors in the package that you can use to suit your needs, which are `MinPriorityQueue`, `MaxPriorityQueue`, and `PriorityQueue`

### 📈 MinPriorityQueue and MaxPriorityQueue

If you want to import to your project, you need to use import or require. However, **you don't need to add this in Leetcode**.
```js
const {
  MinPriorityQueue,
  MaxPriorityQueue
} = require("@datastructures-js/priority-queue");

// or

import {
  MinPriorityQueue,
  MaxPriorityQueue
} from
  "@datastructures-js/priority-queue";
```


You just need to initiate the Priority Queue class, and run the `.enqueue` for each data that you want to insert.

```js
const arr = [10, 22, 4, 5, 21, 8, 9, 59];
const numbersMinQueue = new MinPriorityQueue();
const numbersMaxQueue = new MaxPriorityQueue();

for (const num of arr) {
  numbersMinQueue.enqueue(num);
  numbersMaxQueue.enqueue(num);
}

console.log(numbersMinQueue.toArray());
/** 
[
  { priority: 4, element: 4 },
  { priority: 5, element: 5 },
  { priority: 8, element: 8 },
  { priority: 9, element: 9 },
  { priority: 10, element: 10 },
  { priority: 21, element: 21 },
  { priority: 22, element: 22 },
  { priority: 59, element: 59 }
]
*/
console.log(numbersMaxQueue.toArray());
/** 
[
  { priority: 59, element: 59 },
  { priority: 22, element: 22 },
  { priority: 21, element: 21 },
  { priority: 10, element: 10 },
  { priority: 9, element: 9 },
  { priority: 8, element: 8 },
  { priority: 5, element: 5 },
  { priority: 4, element: 4 }
]
*/
```
Pay attention to the `console.log` result. It returns an array of objects. The object attribute is

```ts
interface PriorityQueueItem { 
  priority: number;
  element: any;
}
```

> Keep in mind, the object is only generated when you are using `MinPriorityQueue()` or `MaxPriorityQueue()`

`priority` attribute is automatically generated by the priority queue, and the `element` attribute is whatever we insert in the `.enqueue()` parameter.

If you are wondering could pass other than the number value to the  `.enqueue()` parameter, and how it will be compared, it's a good thought!

### MinPriorityQueue and MaxPriorityQueue with options
We can pass an option parameter when we initiate the `MinPriorityQueue` or `MaxPriorityQueue` class. It's an object that has a `priority` attribute, and it's required a function
```ts
interface PriorityQueueOptions{
  priority: (element: T) => number;
}
```
Technically, you need to decide which attribute you want to compare if you are not inserting a number. For example, I want to insert this kind of object
```js
const person = {
  name: 'Ray',
  height: 165
};
```
Therefore, you need to add an option in the initialization.
```js
const heightQueue = new MinPriorityQueue({ 
  priority: (person) => person.height 
});
```

This is an example of the whole code.
```js
const heightArr = [
  { name: 'John', height: 170 }, 
  { name: 'Jane', height: 160 }, 
  { name: 'Bob', height: 150 }, 
  { name: 'Mary', height: 180 }
];

const heightQueue = new MinPriorityQueue({ 
  priority: (person) => person.height 
});

for (const height of heightArr) {
    heightQueue.enqueue(height);
}

console.log(heightQueue.toArray())
/** 
[
  { priority: 150, element: { name: 'Bob', height: 150 } },
  { priority: 160, element: { name: 'Jane', height: 160 } },
  { priority: 170, element: { name: 'John', height: 170 } },
  { priority: 180, element: { name: 'Mary', height: 180 } }
]
*/
```
The option also works for the `MaxPriorityQueue`. I prepared a CodeSandbox playground in the of the blog, and you can play around if you want to try the `MaxPriorityQueue`.

### 📈 PriorityQueue
MaxPriorityQueue and MinPriorityQueue prepare everything about the sorting function. I believe some problems require us to modify the sorting rule. That's why the `PrioirtyQueue` class is here. The idea is similar to the options for `MaxPriorityQueue` or `MinPriorityQueue`. It's just a different attribute and function. This is the same function that you need to pass in JavaScript `.sort()` function. Check the docs [here](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort).
```ts
interface PriorityQueueOptions{
  compare: (a: T, b: T) => number;
}
```
For instance, we need to arrange the ages in ascending order, and in case of a tie, we want to sort the names in descending order. This is the initialize option that we need in `PriorityQueue`

```js
const ageQueue = new PriorityQueue({
  compare: (a, b) => {
    if (a.age < b.age) {
      return -1; // don't swap
    } else if (a.age > b.age) {
      return 1; // swap
    } else {
      // If the ages are equal, we sort the names in descending order.
      return b.name.localeCompare(a.name); 
      // or
      // return b.name > a.name ? 1 : -1;
    }
  }
});
```

This is the whole code for the Priority Queue example
```js
// Priority Queue
const ageArr = [
  { name: 'John', age: 33 }, { name: 'Jane', age: 42 }, { name: 'Jack', age: 16 }, { name: 'Jill', age: 35 }, { name: 'Jessica', age: 33 }
]
const ageQueue = new PriorityQueue({
  compare: (a, b) => {
    if (a.age < b.age) {
      return -1;
    } else if (a.age > b.age) {
      return 1;
    } else {
      return b.name.localeCompare(a.name);
      // or
      // return b.name > a.name ? 1 : -1;

    }
  }
});

for (const person of ageArr) {
  ageQueue.enqueue(person);
}
```

## 🔵 `.enqueue()` and `.deqeue()`
**Both time complexity is O(log(n))**

### .enqueue()
- is adding an element based on the comparison with the existing element in the heap.
- will return the PriorityQueue, MaxPrioirityQueue, or MinPriorityQueue object depending on the initialization. Keep in mind, that the return of this function is just pointing to your original heap object. If you are calling `.enqueue()` or `.dequeue()`, it will mutate your heap.

### .dequeue()
- is removing an element from the top of the heap.
- will return the highest priority object that has been removed.

```js
// ... refer to the previous code block in PriorityQueue

// Enqueue
const newAge = { name: 'Monica', age: 27 };
const heap = ageQueue.enqueue(newAge);
console.log(heap);
/** 
PriorityQueue {
  _compare: [Function: compare],
  _heap: CustomHeap {
    _nodes: [ [Object], [Object], [Object], [Object], [Object], [Object] ],
    _leaf: { name: 'Jane', age: 42 },
    _comparator: [Function: compare]
  }
}
*/
console.log(heap.toArray());
/** 
[
  { name: 'Jack', age: 16 },
  { name: 'Monica', age: 27 },
  { name: 'John', age: 33 },
  { name: 'Jessica', age: 33 },
  { name: 'Jill', age: 35 },
  { name: 'Jane', age: 42 }
]
*/

// Dequeue
const topPriority = heap.dequeue()
console.log(topPriority);
/**
{ name: 'Jack', age: 16 }
*/

// Proof of the return `.enqueu()` is just refering to the original heap
console.log(heap.toArray());
/** 
[
  { name: 'Monica', age: 27 },
  { name: 'John', age: 33 },
  { name: 'Jessica', age: 33 },
  { name: 'Jill', age: 35 },
  { name: 'Jane', age: 42 }
]
*/
console.log(ageQueue.toArray());
/** 
[
  { name: 'Monica', age: 27 },
  { name: 'John', age: 33 },
  { name: 'Jessica', age: 33 },
  { name: 'Jill', age: 35 },
  { name: 'Jane', age: 42 }
]
*/
```

## 🔵 .toArray()
**Time complexity is O(n * log(n))**
I assume that you understand the purpose of this function because I used it several times before. It returns a sorted array by priority.

```js
console.log(ageQueue.toArray());
/** 
[
  { name: 'Monica', age: 27 },
  { name: 'John', age: 33 },
  { name: 'Jessica', age: 33 },
  { name: 'Jill', age: 35 },
  { name: 'Jane', age: 42 }
]
*/
```

## 🔵 .size()
**Time complexity is O(1)**
return the number of elements in the heap.
```js
ageQueue.size();
// 5
```

## 🔵 .isEmpty()
**Time complexity is O(1)**
return a boolean whether the heap is empty or not.
```js
ageQueue.isEmpty();
// false
```

## 🔵 .front()
**Time complexity is O(1)**
return the highest priority element
```js
ageQueue.front();
// { name: 'Monica', age: 27 }
```

## 🔵 .back()
**Time complexity is O(1)**
return the lowest priority element
```js
ageQueue.back();
// { name: 'Jane', age: 42 }
```

## 🔵 .clear()
**Time complexity is O(1)**
clear all the elements in the heap
```js
ageQueue.clear();
```

## Conclusion
As a JavaScript developer, I experienced a struggle time when I solved heap questions in Leetcode, and it made me skip those problems because of this package. I took time to understand and learn all of this. I wish this blog could help you to use the package better without feeling like I felt again. Good luck and happy reading 📚.

{% codesandbox 3m2524 %}
Sorry, I failed to make the embed CodeSandbox open my index.js at the beginning. You need to open the index.js first, or opening the CodeDanbox in the new tab will be much easier.

or you can check my repo `data-structures/heap.js`
{% embed https://github.com/raaynaldo/algorithm-ds-playground %}