JavaScript DataStructures: Heap or Priority Queue

A Heap is a special type of binary tree that meets the following criteria:

• Is a complete binary tree;
• The value of each node must be no greater than (or no less than) the value of its child nodes.

A Heap has the following properties:

• Insertion of an element into the Heap has a time complexity of O(logN);
• Deletion of an element from the Heap has a time complexity of O(logN);
• The maximum/minimum value in the Heap can be obtained with O(1) time complexity.

Type of Heaps

• Max Heap: Each node in the Heap has a value no less than its child nodes. Therefore, the top element (root node) has the largest value in the Heap.
• Min Heap: Each node in the Heap has a value no larger than its child nodes. Therefore, the top element (root node) has the smallest value in the Heap.

type of heaps

Implementing Heap in JavaScript

Next, we will implement a Heap. constructor will take a comparator, which will decide the order of elements in Heap (Min or Max)

Concepts:

Follow comments in code.

Code:

Output:

Max Heap:

[
  6, 5, 5, 4, 3,
  3, 2, 2, 1
]

Min Heap

[
  1, 2, 2, 3, 3,
  4, 5, 5, 6
]

You can see, that all returned data is in priority order.

Practice Questions

Problem: Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Solution

const findKthLargest = function(nums, k) {
    const heap = new MaxHeap();
    nums.forEach(num => heap.push(num));
    
    for(let i = 0;i< k-1;i++){
        heap.pop();
    }
    
    return  heap.pop();
};