Implementing a Heap Data Structure in JavaScript

A heap is a specialized tree-based data structure that satisfies the heap property, where for a max heap, the parent node is greater than or equal to its children, and for a min heap, the parent node is less than or equal to its children. In this blog post, we'll explore how to implement a max heap data structure in JavaScript.

Heap Implementation

Below is a step-by-step explanation of each function followed by the complete implementation of a max heap in JavaScript:

1. Constructor:

The constructor initializes an empty array to store the elements of the heap.

2. insert(value):

This method inserts a new element into the heap. It pushes the new value to the end of the array and then calls heapifyUp() to maintain the heap property.

3. heapifyUp():

This method fixes the heap property violations by swapping the newly inserted element with its parent until the heap property is satisfied.

4. removeMax():

This method removes and returns the maximum element from the heap. It replaces the root element with the last element in the array, then calls heapifyDown() to restore the heap property.

5. heapifyDown():

This method fixes heap property violations by recursively swapping the current element with its largest child until the heap property is satisfied.

6. peek():

This method returns the maximum element of the heap without removing it.

7. size() and isEmpty():

These methods return the size of the heap and check if the heap is empty, respectively.

Complete Implementation:

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    // Insert new element into the heap
    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    
    // Fix heap property violations after insertion
    heapifyUp() {
        let currentIndex = this.heap.length - 1;
        while (currentIndex > 0) {
            let parentIndex = Math.floor((currentIndex - 1) / 2);
            if (this.heap[currentIndex] <= this.heap[parentIndex]) break;
            [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
            currentIndex = parentIndex;
        }
    }
    
    // Remove and return the maximum element from the heap
    removeMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return max;
    }
    
    // Fix heap property violations after removal
    heapifyDown() {
        let currentIndex = 0;
        const length = this.heap.length;
        while (true) {
            let leftChildIndex = 2 * currentIndex + 1;
            let rightChildIndex = 2 * currentIndex + 2;
            let largest = currentIndex;
            if (leftChildIndex < length && this.heap[leftChildIndex] > this.heap[largest]) {
                largest = leftChildIndex;
            }
            if (rightChildIndex < length && this.heap[rightChildIndex] > this.heap[largest]) {
                largest = rightChildIndex;
            }
            if (largest === currentIndex) break;
            [this.heap[currentIndex], this.heap[largest]] = [this.heap[largest], this.heap[currentIndex]];
            currentIndex = largest;
        }
    }
    
    // Return the maximum element without removing it
    peek() {
        if (this.heap.length === 0) return null;
        return this.heap[0];
    }
    
    // Return the size of the heap
    size() {
        return this.heap.length;
    }
    
    // Check if the heap is empty
    isEmpty() {
        return this.heap.length === 0;
    }
}

// Example usage:
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(10);
maxHeap.insert(3);
maxHeap.insert(8);
console.log("Max Heap:", maxHeap.heap);
console.log("Removing max element:", maxHeap.removeMax());
console.log("Max Heap after removal:", maxHeap.heap);

This implementation allows us to efficiently insert elements into the heap, remove the maximum element, and peek at the maximum element without violating the heap property. Heap data structures are widely used in various applications, including priority queues, scheduling algorithms, and graph algorithms.

Feel free to experiment with this implementation and explore other variations of heap data structures, such as min heaps and binary heaps.