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 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.
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.
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.
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.
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
interface PriorityQueueItem {
priority: number;
element: any;
}
Keep in mind, the object is only generated when you are using
MinPriorityQueue()orMaxPriorityQueue()
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
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
const person = {
name: 'Ray',
height: 165
};
Therefore, you need to add an option in the initialization.
const heightQueue = new MinPriorityQueue({
priority: (person) => person.height
});
This is an example of the whole code.
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.
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
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
// 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.
// ... 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.
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.
ageQueue.size();
// 5
🔵 .isEmpty()
Time complexity is O(1)
return a boolean whether the heap is empty or not.
ageQueue.isEmpty();
// false
🔵 .front()
Time complexity is O(1)
return the highest priority element
ageQueue.front();
// { name: 'Monica', age: 27 }
🔵 .back()
Time complexity is O(1)
return the lowest priority element
ageQueue.back();
// { name: 'Jane', age: 42 }
🔵 .clear()
Time complexity is O(1)
clear all the elements in the heap
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 📚.
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
Algorithm and Data Structure Playground
Getting Start
Install all Packages
npm install
Go to your file directory that you want to run
cd data-structures
Run the file with node
node heap.js
Top comments (0)