A heap is a specialized binary tree-based data structure that satisfies the heap property. In a heap, every parent node has a value that is either greater than or less than (depending on the type of heap) the values of its children nodes. This property ensures that the highest (or lowest) priority element is always at the root of the heap.

Types of Heaps:

There are two main types of heaps: max heaps and min heaps.

• Max Heap: In a max heap, the value of each parent node is greater than or equal to the values of its children nodes.

• Min Heap: In a min heap, the value of each parent node is less than or equal to the values of its children nodes.

Heap Operations:

• Insertion: To insert an element into a heap, it is added as a new leaf node and then "bubbled up" (or "sifted up") to its correct position to maintain the heap property.

• Deletion: Removing an element from a heap involves replacing the root node with the last leaf node, and then "bubbling down" (or "sifted down") the new root to its correct position.

• Peek: Returns the root element of the heap without removing it.

• Heapify: Building a heap from an array of elements by repeatedly calling the insertion operation.

class MinHeap {
  private heap: number[];

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

  insert(value: number): void {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index: number): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] < this.heap[parentIndex]) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return minValue;
  }


  bubbleDown(index: number): void {
    while (index < this.heap.length) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let smallestIndex = index;
      if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallestIndex]) {
        smallestIndex = leftChildIndex;
      }
      if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallestIndex]) {
        smallestIndex = rightChildIndex;
      }
      if (smallestIndex !== index) {
        [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
        index = smallestIndex;
      } else {
        break;
      }
    }
  }

  peek(): number | undefined {
    return this.heap[0];
  }

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

  isEmpty(): boolean {
    return this.heap.length === 0;
  }
}

// Example usage:
const heap = new MinHeap();
heap.insert(5);
heap.insert(10);
heap.insert(3);
console.log(heap.extractMin()); // Output: 3

When to use Heaps?

Heaps are commonly used in scenarios where you need to efficiently manage elements based on their priority. Here are some situations where heaps are typically used:

• Priority Queues: Heaps are ideal for implementing priority queues, where elements are processed in order of their priority. Priority queues are used in various applications such as task scheduling, job processing, and event-driven systems.

• Sorting Algorithms: Heapsort, a comparison-based sorting algorithm, uses heaps to efficiently sort elements in ascending or descending order. Heapsort has a time complexity of O(n log n), making it suitable for sorting large datasets.

• Graph Algorithms: Heaps are used in graph algorithms such as Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm. In Dijkstra's algorithm, a min heap is used to efficiently select the next vertex with the shortest distance from a source vertex.

• Memory Management: Heaps are used in memory management systems to allocate and deallocate memory blocks dynamically. Memory allocation algorithms such as the buddy system and the binomial heap allocation algorithm rely on heaps to efficiently manage memory blocks.

Task Scheduling: Heaps can be used to schedule tasks or jobs based on their priority or deadline. In task scheduling applications, tasks with higher priority or earlier deadlines are executed first, ensuring optimal resource utilization.

Heaps are a versatile data structure with various applications, including priority queues, sorting algorithms (e.g., heap sort), and graph algorithms (e.g., Dijkstra's shortest path algorithm). Understanding heaps and their operations is essential for any programmer seeking to solve problems efficiently in areas such as algorithm design, optimization, and data analysis. With the knowledge gained from this article and the provided TypeScript examples, you're now well-equipped to leverage heaps in your projects and tackle complex problems with confidence.