Introduction
Hey there, fellow JavaScript devs! In the event you’re right here, chances are high you are diving into the heap of questions on LeetCode – been there, carried out that. I get it. I used to wrestle with those self same challenges, and now I need to be the good friend who helps you thru the wrestle. So, should you’re scratching your head over heap issues, loosen up, I’ve obtained your again. JavaScript does not have any Precedence Queue built-in operate. That you must perceive these vital codes to unravel heap questions in LeetCode with JavaScript.
JavaScript in Leetcode
In accordance with the LeetCode help web page, they make the most of @datastructures-js/priority-queue bundle. It talked about that the model is v4.1. Nevertheless, after exploring the bundle, I noticed we may additionally use the v5. Due to this fact, if you wish to go to the official documentation in Github, it’s good to just be sure you are taking a look at v5. I consider v5 is the complement of v4, so that you simply have to verify the v5 docs.
Heap (Precedence Queue) in Common
I can’t talk about how the heap works in depth as a result of that is not the aim of this weblog. The principle concept of a heap is it’ll preserve sustaining the order of all the info. If you’re utilizing the Minimal Precedence Queue, the primary component would be the smallest. Due to this fact, it is the identical concept for the Most Precedence Queue
Check out the Min Heap simulation right here.
Visualization Hyperlink:
https://www.cs.usfca.edu/~galles/visualization/Heap.html
🔵 Initialization
There are three constructors within the bundle that you should utilize to fit your wants, that are MinPriorityQueue, MaxPriorityQueue, and PriorityQueue
📈 MinPriorityQueue and MaxPriorityQueue
If you wish to import to your undertaking, it’s good to use import or require. Nevertheless, you needn’t add this in Leetcode.
const {
MinPriorityQueue,
MaxPriorityQueue
} = require("@datastructures-js/priority-queue");
// or
import {
MinPriorityQueue,
MaxPriorityQueue
} from
"@datastructures-js/priority-queue";
You simply have to provoke the Precedence Queue class, and run the .enqueue for every knowledge that you simply need 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 }
]
*/
Take note of the console.log outcome. It returns an array of objects. The article attribute is
interface PriorityQueueItem {
precedence: quantity;
component: any;
}
Consider, the item is barely generated when you find yourself utilizing
MinPriorityQueue()orMaxPriorityQueue()
precedence attribute is routinely generated by the precedence queue, and the component attribute is no matter we insert within the .enqueue() parameter.
If you’re questioning may go aside from the quantity worth to the .enqueue() parameter, and the way it will likely be in contrast, it is a good thought!
MinPriorityQueue and MaxPriorityQueue with choices
We are able to go an choice parameter after we provoke the MinPriorityQueue or MaxPriorityQueue class. It is an object that has a precedence attribute, and it is required a operate
interface PriorityQueueOptions{
precedence: (component: T) => quantity;
}
Technically, it’s good to determine which attribute you need to examine in case you are not inserting a quantity. For instance, I need to insert this sort of object
const particular person = {
identify: 'Ray',
peak: 165
};
Due to this fact, it’s good to add an choice within the initialization.
const heightQueue = new MinPriorityQueue({
precedence: (particular person) => particular person.peak
});
That is an instance of the entire code.
const heightArr = [
{ name: 'John', height: 170 },
{ name: 'Jane', height: 160 },
{ name: 'Bob', height: 150 },
{ name: 'Mary', height: 180 }
];
const heightQueue = new MinPriorityQueue({
precedence: (particular person) => particular person.peak
});
for (const peak of heightArr) {
heightQueue.enqueue(peak);
}
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 choice additionally works for the MaxPriorityQueue. I ready a Replit playground within the of the weblog, and you’ll mess around if you wish to attempt the MaxPriorityQueue.
📈 PriorityQueue
MaxPriorityQueue and MinPriorityQueue put together all the pieces concerning the sorting operate. I consider some issues require us to change the sorting rule. That is why the PrioirtyQueue class is right here. The concept is much like the choices for MaxPriorityQueue or MinPriorityQueue. It is only a completely different attribute and performance. This is similar operate that it’s good to go in JavaScript .type() operate. Verify the docs here.
interface PriorityQueueOptions{
examine: (a: T, b: T) => quantity;
}
As an illustration, we have to organize the ages in ascending order, and in case of a tie, we need to type the names in descending order. That is the initialize choice that we’d like in PriorityQueue
const ageQueue = new PriorityQueue({
examine: (a, b) => {
if (a.age < b.age) {
return -1; // do not swap
} else if (a.age > b.age) {
return 1; // swap
} else {
// If the ages are equal, we type the names in descending order.
return b.identify.localeCompare(a.identify);
// or
// return b.identify > a.identify ? 1 : -1;
}
}
});
That is the entire code for the Precedence Queue instance
// Precedence 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({
examine: (a, b) => {
if (a.age < b.age) {
return -1;
} else if (a.age > b.age) {
return 1;
} else {
return b.identify.localeCompare(a.identify);
// or
// return b.identify > a.identify ? 1 : -1;
}
}
});
for (const particular person of ageArr) {
ageQueue.enqueue(particular person);
}
🔵 .enqueue() and .deqeue()
Each time complexity is O(log(n))
.enqueue()
- is including a component primarily based on the comparability with the present component within the heap.
- will return the PriorityQueue, MaxPrioirityQueue, or MinPriorityQueue object relying on the initialization. Consider, that the return of this operate is simply pointing to your unique heap object. If you’re calling
.enqueue()or.dequeue(), it’ll mutate your heap.
.dequeue()
- is eradicating a component from the highest of the heap.
- will return the best precedence object that has been eliminated.
// ... confer with the earlier code block in PriorityQueue
// Enqueue
const newAge = { identify: '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: { identify: '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);
/**
{ identify: 'Jack', age: 16 }
*/
// Proof of the return `.enqueu()` is simply refering to the unique 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 simply perceive the aim of this operate as a result of I used it a number of instances earlier than. It returns a sorted array by precedence.
console.log(ageQueue.toArray());
/**
[
{ name: 'Monica', age: 27 },
{ name: 'John', age: 33 },
{ name: 'Jessica', age: 33 },
{ name: 'Jill', age: 35 },
{ name: 'Jane', age: 42 }
]
*/
🔵 .measurement()
Time complexity is O(1)
return the variety of components within the heap.
ageQueue.measurement();
// 5
🔵 .isEmpty()
Time complexity is O(1)
return a boolean whether or not the heap is empty or not.
ageQueue.isEmpty();
// false
🔵 .entrance()
Time complexity is O(1)
return the best precedence component
ageQueue.entrance();
// { identify: 'Monica', age: 27 }
🔵 .again()
Time complexity is O(1)
return the bottom precedence component
ageQueue.again();
// { identify: 'Jane', age: 42 }
🔵 .clear()
Time complexity is O(1)
clear all the weather within the heap
ageQueue.clear();
Conclusion
As a JavaScript developer, I skilled a wrestle time once I solved heap questions in Leetcode, and it made me skip these issues due to this bundle. I took time to know and be taught all of this. I want this weblog may assist you to make use of the bundle higher with out feeling like I felt once more. Good luck and completely satisfied studying 📚.
Sorry, I didn’t make the embed CodeSandbox open my index.js originally. That you must open the index.js first, or opening the CodeDanbox within the new tab shall be a lot simpler.
