Heap Data Structure in JavaScript

1 Binary Heap Introduction

A Heap is a special Tree-based data structure that satisfies two critical properties:

Complete Binary Tree: All levels are completely filled except possibly the last level, and the last level has all keys as left as possible. This property makes them perfectly suited to be represented using arrays.
Heap Property:
- Min-Heap: The key at the root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in that Tree.
- Max-Heap: The key at the root must be maximum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in that Tree.

Representing Binary Heaps using Arrays

Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays, which makes it extremely space efficient.

The root element will be at Arr[0].
For any ith node, i.e., Arr[i]:
- Parent Node: Arr[Math.floor((i-1)/2)]
- Left Child Node: Arr[(2*i) + 1]
- Right Child Node: Arr[(2*i) + 2]

Getting Minimum/Maximum Element: In a Min-Heap, the minimum element is always present at the root node (Arr[0]). In a Max-Heap, the maximum element is at Arr[0]. Time Complexity: O(1)

2 Insertion and Deletion in Heap

1. Insertion in a Heap

Algorithm:

Insert the new element at the end of the tree (end of the array) so that it remains a complete binary tree.
Compare the new node with its parent.
If it violates the heap property (e.g., in a Max-Heap, if the new node is greater than its parent), swap them.
Repeat this "Heapify Up" process until the heap property is restored.

Time Complexity: O(log N) (Height of the complete binary tree).

2. Deletion in a Heap

The standard deletion operation on a Heap is to delete the element present at the root node (i.e., Extract-Max or Extract-Min). Algorithm:

Replace the root element with the last element in the tree (last element of the array).
Delete the last element.
Compare the new root with its children.
If it violates the heap property, swap it with the appropriate child (largest child for Max-Heap, smallest for Min-Heap).
Repeat this "Heapify Down" process until the heap property is restored.

Time Complexity: O(log N).

3 Heap Sort

Heap Sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end.

Heap Sort Algorithm:

Build a Max Heap: Apply the heapify procedure to all non-leaf nodes in a bottom-up order (O(N) time).
At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap, and reduce the size of the heap by 1.
Heapify the root of the tree.
Repeat the above steps while the size of the heap is greater than 1.

JavaScript Implementation:

function heapify(arr, n, i) {
  let largest = i; // Initialize largest as root
  let l = 2 * i + 1; // left child
  let r = 2 * i + 2; // right child
 
  // If left child is larger than root
  if (l < n && arr[l] > arr[largest]) {
    largest = l;
  }
 
  // If right child is larger than largest so far
  if (r < n && arr[r] > arr[largest]) {
    largest = r;
  }
 
  // If largest is not root
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
  }
}
 
function heapSort(arr) {
  let n = arr.length;
 
  // Build heap (rearrange array)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
 
  // One by one extract an element from heap
  for (let i = n - 1; i > 0; i--) {
    // Move current root to end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // Call max heapify on the reduced heap
    heapify(arr, i, 0);
  }
  return arr;
}

Time Complexity: O(N log N) overall. Building the initial heap takes O(N) time. Important Notes:

Heap sort is an in-place algorithm.
Its typical implementation is not stable.

4 Advanced Interview Problems using Heaps

Problem 1: Sort a K-Sorted Array

Given an array of size n, where every element is at most k positions away from its target position, sort the array efficiently.

Approach using Heap:

Create a Min-Heap of size k+1 with the first k+1 elements. This takes O(k) time.
One by one, remove the minimum element from the heap, put it in the result array, and add a new element from the remaining elements in the array to the heap.

// Using JS array sorting as a mock priority queue for simplicity
function sortK(arr, n, k) {
  // Insert first k+1 items in a priority queue
  let size = n === k ? k : k + 1;
  let pq = arr.slice(0, size);
  pq.sort((a, b) => a - b);
  
  let index = 0;
  for (let i = k + 1; i < n; i++) {
    arr[index++] = pq.shift(); // extract min
    pq.push(arr[i]);           // push next
    pq.sort((a, b) => a - b);  // mock heapify
  }
  
  while (pq.length > 0) {
    arr[index++] = pq.shift();
  }
}

Time Complexity: O(k + (n-k) log k) Auxiliary Space: O(k)

Problem 2: Buy Maximum Items with Given Sum

Given an array arr[] consisting of the costs of toys and an integer K depicting the amount of money available to purchase toys. Find the maximum number of toys one can buy.

Approach using Priority Queue (Min-Heap): Insert all elements into a priority queue (Min-Heap). Remove elements one by one and keep adding their costs to a sum variable. Stop when adding the next minimum element would exceed K.

function maxToys(arr, n, k) {
  // Mock priority queue
  let pq = [...arr];
  pq.sort((a, b) => a - b); // Sorting serves as our Min-Heap extraction order
  
  let count = 0;
  for (let i = 0; i < pq.length; i++) {
    if (pq[i] <= k) {
      count++;
      k -= pq[i];
    } else {
      break;
    }
  }
  return count;
}

Time Complexity: O(N log N) due to the initial heap building/sorting. Auxiliary Space: O(N)

Problem 3: K Largest Elements in an Array

Given an array of N numbers, find the K largest elements.

Method 1: Use Sorting Sort the array in descending order and print the first K elements.

Time Complexity: O(N log N)
Auxiliary Space: O(1)

Method 2: Use Max Heap

Build a Max Heap tree in O(N) time.
Use Extract Max K times to get K maximum elements.

Time Complexity: O(N + K log N)

Method 3: Use Min Heap (Optimal for large N)

Build a Min Heap of the first K elements (O(K) time).
For each element from the (K+1)th to the Nth element:
- If the element is greater than the root of the Min Heap, replace the root with the element and heapify.
- Else, ignore it.
Finally, the Min Heap contains the K largest elements.

// Method 1 Implementation
function kLargest(arr, n, k) {
  // Sort the given array arr in reverse order.
  arr.sort((a, b) => b - a);
  
  // Print the first kth largest elements
  for (let i = 0; i < k; i++) {
    console.log(arr[i]);
  }
}

Time Complexity (Method 3): O(K + (N - K) log K) which simplifies to O(N log K) Auxiliary Space: O(K)

Problem 4: K Closest Elements

Given a sorted array arr[] and a value X, find the K closest elements to X in arr[]. (Note: if X is present in the array, it should not be in the output, only the other closest elements are required).

Simple Solution: Do a linear search for the crossover point (the point before which elements are smaller than or equal to X and after which elements are greater). Then compare elements on both sides of the crossover point to print K closest elements. Time Complexity: O(N).

Optimized Solution (Using Binary Search): Find the crossover point using Binary Search in O(log N) time. Once we find the index of the crossover point, we can print K closest elements using two pointers in O(K) time.

function findCrossOver(arr, low, high, x) {
  // Base cases
  if (arr[high] <= x) {
    return high;
  }
  if (arr[low] > x) {
    return low;
  }
  
  let mid = Math.floor((low + high) / 2);
  
  // Check if mid is the crossover point
  if (arr[mid] <= x && arr[mid + 1] > x) {
    return mid;
  }
  
  // If x is greater than mid, then crossover point lies in right half
  if (arr[mid] < x) {
    return findCrossOver(arr, mid + 1, high, x);
  }
  
  // Crossover point lies in left half
  return findCrossOver(arr, low, mid - 1, x);
}
 
function printKclosest(arr, x, k, n) {
  // Find the crossover point
  let l = findCrossOver(arr, 0, n - 1, x);
  let r = l + 1; // Right pointer
  let count = 0; // To keep track of count of elements already printed
  
  // If x is present in arr[], reduce left pointer
  if (arr[l] === x) {
    l--;
  }
  
  // Compare elements on left and right of crossover
  while (l >= 0 && r < n && count < k) {
    if (x - arr[l] < arr[r] - x) {
      console.log(arr[l]);
      l--;
    } else {
      console.log(arr[r]);
      r++;
    }
    count++;
  }
  
  // If there are no more elements on right side, print left elements
  while (count < k && l >= 0) {
    console.log(arr[l]);
    l--;
    count++;
  }
  
  // If there are no more elements on left side, print right elements
  while (count < k && r < n) {
    console.log(arr[r]);
    r++;
    count++;
  }
}

Time Complexity: O(log N + K) Auxiliary Space: O(1) (or O(log N) due to recursive call stack of Binary Search).

Binary Search Tree Introduction to Hashing