Uzma's Blog

Binary Heaps

Uzma's photo
Uzma
·

8 min read

Binary heaps are fundamental data structures used in computer science and software development to efficiently manage and organize data with priority-based operations. They play a crucial role in various algorithms like Dijkstra's shortest path algorithm, heap sort, and implementing priority queues. In this blog, we'll dive into the world of binary heaps, exploring their concepts, implementation, and practical use cases in JavaScript.

Understanding Binary Heaps: A binary heap is a complete binary tree with a specific ordering property that ensures efficient operations. There are two main types of binary heaps: max heaps and min heaps. In a max heap, each parent node has a value greater than or equal to its children, making the root node the maximum element. Conversely, in a min heap, each parent node has a value less than or equal to its children, making the root node the minimum element.

Key Operations: Binary heaps support two primary operations: insertion and removal. Let's delve into how these operations work:

  1. Insertion: When inserting an element into a binary heap, it's added as the last node in the tree and then "bubbled up" or "swapped up" to its correct position to maintain the heap property. In a max heap, this means comparing the inserted element with its parent and swapping them if necessary until the heap property is satisfied.

  2. Removal: When removing the root element (max or min) from the heap, it's replaced with the last element in the heap This element is then "bubbled down" or "swapped down" to its correct position by comparing it with its children and swapping as needed.

Implementation in JavaScript:

Let's see how we can implement a min binary heap in JavaScript using an array:

class MinBinaryHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;

        while (currentIndex > 0) {
            const parentIndex = Math.floor((currentIndex - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[currentIndex]) break;

            [this.heap[parentIndex], this.heap[currentIndex]] = [this.heap[currentIndex], this.heap[parentIndex]];
            currentIndex = parentIndex;
        }
    }

    removeMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const minValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        let currentIndex = 0;
while (true) {
            const leftChildIndex = 2 * currentIndex + 1;
            const rightChildIndex = 2 * currentIndex + 2;
            let smallestChildIndex = currentIndex;

            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallestChildIndex]) {
                smallestChildIndex = leftChildIndex;
            }
            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallestChildIndex]) {
                smallestChildIndex = rightChildIndex;
            }
            if (smallestChildIndex === currentIndex) break;

            [this.heap[currentIndex], this.heap[smallestChildIndex]] = [this.heap[smallestChildIndex], this.heap[currentIndex]];
            currentIndex = smallestChildIndex;
        }

        return minValue;
    }
}

Let's see how we can implement a max binary heap in JavaScript using an array:

class MaxBinaryHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this.bubbleUp();
    } 

    bubbleUp() {
        let index = this.heap.length - 1;
        const element = this.heap[index];


while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];

            if (element <= parent) break;

            this.heap[parentIndex] = element;
            this.heap[index] = parent;
            index = parentIndex;
        }
 }

    extractMax() {
        const max = this.heap[0];
        const end = this.heap.pop();

        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown();
        }

        return max;
    }

    sinkDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swap === null && rightChild > element) ||
                    (swap !== null && rightChild > leftChild)
                ) {
                    swap = rightChildIndex;
                }
            }

if (swap === null) break;

            this.heap[index] = this.heap[swap];
            this.heap[swap] = element;
            index = swap;
        }
    }
}

// Example usage
const maxHeap = new MaxBinaryHeap();
maxHeap.insert(41);
maxHeap.insert(39);
maxHeap.insert(33);
maxHeap.insert(18);
maxHeap.insert(27);
maxHeap.insert(12);
maxHeap.insert(55);

console.log(maxHeap.heap); // [55, 39, 41, 18, 27, 12, 33]
console.log(maxHeap.extractMax()); // 55
console.log(maxHeap.heap); // [41, 39, 33, 18, 27, 12]

Practical Use Cases: Binary heaps have various real-world applications, including:

  1. Priority Queues: Binary heaps can be used to implement priority queues, where elements are dequeued based on their priority.
class Node {
  constructor(val, priority) {
    this.val = val;
    this.priority = priority;
  }
}

class PQ {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    let index = this.values.length - 1;
    const current = this.values[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.values[parentIndex];

      if (parent.priority <= current.priority) {
        this.values[parentIndex] = current;
        this.values[index] = parent;
        index = parentIndex;
      } else break;
    }
  }
  dequeue() {
    const max = this.values[0];
    const end = this.values.pop();
    this.values[0] = end;

    let index = 0;
    const length = this.values.length;
    const current = this.values[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
 let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild.priority > current.priority) swap = leftChildIndex;
      }
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild.priority > current.priority) ||
          (swap !== null && rightChild.priority > leftChild.priority)
        )
          swap = rightChildIndex;
      }

      if (swap === null) break;
      this.values[index] = this.values[swap];
      this.values[swap] = current;
      index = swap;
    }

    return max;
  }
}

const tree = new BH();
tree.enqueue(3, 2);
tree.enqueue(4, 5);
tree.enqueue(31, 1);
tree.enqueue(6, 3);
console.log(tree.dequeue()); // 4
console.log(tree.dequeue()); // 6
console.log(tree.dequeue()); // 3
console.log(tree.dequeue()); // 31
  1. Dijkstra's Algorithm: It can be employed in the famous shortest path algorithm to find the shortest path between nodes in a graph.
class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }

  dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    // Build up initial state
    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }

    // As long as there is something to visit
    while (nodes.values.length) {
      smallest = nodes.dequeue().val;

      if (smallest === finish) {
        // Build up path to return at the end
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
          let nextNode = this.adjacencyList[smallest][neighbor];
          // Calculate new distance to neighboring node
          let potential = distances[smallest] + nextNode.weight;

          if (potential < distances[nextNode.node]) {
            // Updating new smallest distance to neighbor
            distances[nextNode.node] = potential;
            // Updating previous - How we got to neighbor
            previous[nextNode.node] = smallest;
            // Enqueue in priority queue with new priority
            nodes.enqueue(nextNode.node, potential);
          }
        }
      }
    }

    return path.concat(smallest).reverse();
  }
}

// Example usage
const graph = new WeightedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);

console.log(graph.dijkstra('A', 'E')); // Output: [ 'A', 'C', 'D', 'F', 'E' ]
  1. Heap Sort: Binary heaps are at the core of the heap sort algorithm, which efficiently sorts an array in place.
function heapSort(arr) {
  // Build max heap
  function buildMaxHeap(array) {
    const length = array.length;
    const start = Math.floor(length / 2) - 1;

    for (let i = start; i >= 0; i--) {
      heapify(array, length, i);
    }
  }

  // Heapify a subtree rooted with node i
  function heapify(array, length, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
      largest = left;
 }

    if (right < length && array[right] > array[largest]) {
      largest = right;
    }

    if (largest !== i) {
      [array[i], array[largest]] = [array[largest], array[i]];
      heapify(array, length, largest);
    }
  }

  // Perform heap sort
  const length = arr.length;

  // Build the max heap
  buildMaxHeap(arr);
 // Extract elements from the heap one by one
  for (let i = length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }

  return arr;
}

// Example usage
const unsortedArray = [9, 4, 7, 2, 5, 1, 8, 3, 6];
const sortedArray = heapSort(unsortedArray.slice());

console.log("Unsorted Array:", unsortedArray);
console.log("Sorted Array:", sortedArray);
  1. Top K Elements: Binary heaps are useful for maintaining a collection of the top K elements from a dataset.

example :

class Heap {
  constructor(arr) {
    this.arr = arr;
    this.n = arr.length;
  }

  swap(i, j) {
    const temp = this.arr[i];
    this.arr[i] = this.arr[j];
    this.arr[j] = temp;
  }

  parent(i) {
    return Math.floor((i - 1) / 2);
  }

  left(i) {
    return 2 * i + 1;
  }

  right(i) {
    return 2 * i + 2;
  }

  heapify(i) {
    let l = this.left(i);
    let r = this.right(i);
    let m = i;

    if (l < this.n && this.arr[i] < this.arr[l]) {
      m = l;
    }
    if (r < this.n && this.arr[m] < this.arr[r]) {
      m = r;
    }
    if (m !== i) {
      this.swap(m, i);
      this.heapify(m);
    }
  }

  extractMax() {
    if (!this.n) {
      return -1;
    }

    let m = this.arr[0];
    this.arr[0] = this.arr[this.n-- - 1];
    this.heapify(0);

    return m;
  }
}

function kthGreatest(arr, k) {
  const h = new Heap(arr);

  for (let i = 1; i < k; i++) {
    h.extractMax();
  }

  return h.extractMax();
}

// Driver Code
const arr = [20, 15, 18, 8, 10, 5, 17];
const k = 4;

console.log(kthGreatest(arr, k));

BigO of Binary Heap:

One of our favourite sections is discussing the BigO of data structures. What’s the point of implementing a Binary Heap over an array? Time complexity is greatly reduced when making use of a binary heap over an array. Insertion and Deletion in a binary heap are very fast, both operations are done in O(logn) compared to O(n) when using arrays. It is very worth implementing a binary heap if your goal is to constantly add and delete nodes.