Binary Heaps

Introduction

Binary heaps are a fundamental data structure used in computer science, particularly in algorithms that require efficient priority queue operations. A binary heap is a complete binary tree where each node satisfies the heap property. There are two types of binary heaps:

• Max Heap: In a max heap, for every node i, the value of i is greater than or equal to the values of its children.
• Min Heap: In a min heap, for every node i, the value of i is less than or equal to the values of its children.

Binary heaps are typically implemented using arrays due to their efficient memory usage and fast access times. This tutorial will cover the implementation, operations, and applications of binary heaps.

Implementation

Array Representation

A binary heap can be efficiently represented as an array. For a node at index i:

• The parent node is at index (i - 1) / 2.
• The left child is at index 2 * i + 1.
• The right child is at index 2 * i + 2.

Code Example

Here's a basic implementation of a binary heap in JavaScript:

class BinaryHeap {
    constructor(comparator = (a, b) => a - b) {
        this.heap = [];
        this.comparator = comparator;
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    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 (this.comparator(element, parent) >= 0) break;

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

        this.heap[index] = element;
    }

    extract() {
        const min = this.heap[0];
        const end = this.heap.pop();

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

        return min;
    }

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

        while (true) {
            let leftChildIndex, rightChildIndex;
            let leftChild, rightChild;
            let swap = null;

            leftChildIndex = 2 * index + 1;
            rightChildIndex = 2 * index + 2;

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

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

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

        this.heap[index] = element;
    }
}

Operations

Insertion

To insert a new element into the heap, add it to the end of the array and then "bubble up" the element to its correct position by comparing it with its parent. If the element is smaller (in a min heap) or larger (in a max heap) than its parent, swap them.

Extraction

To extract the root element (minimum in a min heap, maximum in a max heap), replace it with the last element in the array and then "sink down" the new root to its correct position by comparing it with its children. Swap it with the smaller child (in a min heap) or larger child (in a max heap) until it is in the correct position.

Best Practices

1. Use Arrays for Efficiency: Binary heaps are best implemented using arrays due to their efficient memory usage and fast access times.
2. Maintain Heap Property: Always ensure that the heap property is maintained after every insertion or extraction operation.
3. Choose Comparator Carefully: The comparator function should be chosen based on whether you want a min heap or max heap.

Applications

Binary heaps are widely used in various applications, including:

• Priority Queues: Binary heaps are used to implement priority queues efficiently.
• Heap Sort: Heap sort is an efficient comparison-based sorting algorithm that uses binary heaps.
• Dijkstra's Algorithm: Used for finding the shortest path from a single source vertex to all other vertices in a graph.

Conclusion

Binary heaps are a powerful data structure with numerous applications. Understanding their implementation and operations can significantly enhance your ability to solve complex problems efficiently. By following best practices and understanding real-world applications, you can leverage binary heaps effectively in your projects.