DEV Community

Cover image for ⚙️ Leetcode Heap (Priority Queue) in JavaScript
Raynaldo Sutisna
Raynaldo Sutisna

Posted on

⚙️ Leetcode Heap (Priority Queue) in JavaScript

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.

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.
Visualiation

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";


Enter fullscreen mode Exit fullscreen mode

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 }
]
*/


Enter fullscreen mode Exit fullscreen mode

Pay attention to the console.log result. It returns an array of objects. The object attribute is



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


Enter fullscreen mode Exit fullscreen mode

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



interface PriorityQueueOptions{
  priority: (element: T) => number;
}


Enter fullscreen mode Exit fullscreen mode

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
};


Enter fullscreen mode Exit fullscreen mode

Therefore, you need to add an option in the initialization.



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


Enter fullscreen mode Exit fullscreen mode

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 } }
]
*/


Enter fullscreen mode Exit fullscreen mode

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;
}


Enter fullscreen mode Exit fullscreen mode

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


Enter fullscreen mode Exit fullscreen mode

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


Enter fullscreen mode Exit fullscreen mode

🔵 .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 }
]
*/


Enter fullscreen mode Exit fullscreen mode

🔵 .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 }
]
*/


Enter fullscreen mode Exit fullscreen mode

🔵 .size()

Time complexity is O(1)
return the number of elements in the heap.



ageQueue.size();
// 5


Enter fullscreen mode Exit fullscreen mode

🔵 .isEmpty()

Time complexity is O(1)
return a boolean whether the heap is empty or not.



ageQueue.isEmpty();
// false


Enter fullscreen mode Exit fullscreen mode

🔵 .front()

Time complexity is O(1)
return the highest priority element



ageQueue.front();
// { name: 'Monica', age: 27 }


Enter fullscreen mode Exit fullscreen mode

🔵 .back()

Time complexity is O(1)
return the lowest priority element



ageQueue.back();
// { name: 'Jane', age: 42 }


Enter fullscreen mode Exit fullscreen mode

🔵 .clear()

Time complexity is O(1)
clear all the elements in the heap



ageQueue.clear();


Enter fullscreen mode Exit fullscreen mode

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)