Lesson 2
Heaps and Priority Queues in JavaScript
Lesson Overview

Welcome to our exploration of the intriguing worlds of heaps and priority queues. These are powerful data structures used extensively across a range of applications, from job scheduling systems to modeling the stock market. Heaps can efficiently solve problems involving intervals, nth largest elements, and even sorting. JavaScript, with libraries like heap-js, provides functions to interact with a list as if it were a heap.

Quick Overview & Motivation

Heaps are a category of binary trees where every node has a value either less than the value of any of its children, in which case it is called a MinHeap, or greater than or equal to the value of any of its children, in which case it is called a MaxHeap. This property allows us to repeatedly access the smallest or largest element, respectively, enabling us to solve numerous problems effortlessly. For example, if you want to find the n-th largest number in a list, using sorting to solve this problem can be very expensive. By leveraging a MaxHeap data structure, this problem can be solved efficiently. Priority queues are an abstraction over heaps that store elements according to their priorities. They are used when objects need to be processed based on priority. For instance, scheduling CPU tasks based on priority is a real-life scenario for priority queues.

Complexity Considerations

Heaps provide efficient time complexities for insertion, deletion, and access operations.

  • Insertion of a new element into the heap takes O(logn)O(\log n) time.
  • Deletion, particularly removal of the maximum or minimum element, also takes O(logn)O(\log n) time.
  • Accessing the maximum or minimum element is done in O(1)O(1) time.
Example: Finding the n-th Largest Element

Consider the problem of finding the n-th largest element in a list of integers. To achieve this, using a MaxHeap significantly reduces the complexity compared to sorting the entire list.

Here is how you can do it in JavaScript:

JavaScript
1const { Heap } = require('heap-js'); 2 3function findNthLargest(nums, n) { 4 // Create a MaxHeap by providing a comparator function 5 const maxHeap = new Heap((a, b) => b - a); // MaxHeap comparator (larger elements come first) 6 7 nums.forEach(num => maxHeap.push(num)); // Add every element to the heap 8 let result = null; 9 10 for (let i = 0; i < n; i++) { 11 result = maxHeap.pop(); // Extract n largest elements from the heap 12 } 13 14 return result; // The last extracted element is the nth largest element 15} 16 17// Test 18console.log(findNthLargest([3, 2, 1, 5, 6, 4], 2)); // Output: 5 19
What's Next: Practice!

Let's plunge into the exercises, trusting that the best way to learn is by doing. As we solve various problems, you'll build a solid understanding of how these powerful tools can be employed to simplify complex tasks. This will not only prepare you for your interviews but also cultivate a mindset for problem-solving. Welcome aboard!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.