Heap Introduction

A heap is a type of binary tree where each level is fully filled with nodes except possibly the last one, which is filled from left to right. Each node in a heap contains a value, and the arrangement of these values follows a specific rule called the "heap property":

In a Max-Heap, each parent node's value is greater than or equal to the values of its children.
In a Min-Heap, each parent node's value is less than or equal to the values of its children.

This structure ensures that the tree is always as balanced as possible, making certain operations efficient.

Max-Heap :

In a Max-Heap, every element follows a rule: the value (or "key") of each parent node is greater than or equal to the values of its child nodes. So, when you move up from any node in the tree, you'll see a sequence of keys that either stays the same or increases. When you move down from any node, the sequence of keys either stays the same or decreases.

In simple terms:

The biggest value in a Max-Heap is always at the top (the root).
As you move down the tree, the values get smaller.

Min-Heap :

In a Min-Heap, every element follows a rule: the value (or "key") of each parent node is less than or equal to the values of its child nodes. So, when you move up from any node in the tree, you'll see a sequence of keys that either stays the same or decreases. When you move down from any node, the sequence of keys either stays the same or increases.

In simple terms:

The smallest value in a Min-Heap is always at the top (the root).
As you move down the tree, the values get larger.

Understanding Binary Heap:

A binary heap is like a special kind of binary tree with two important rules:

Shape Property: Every level of the tree is filled except possibly the last level, which is filled from left to right.
Heap Property: Every parent node in the tree has a value that's either greater than or equal to (in a Max-Heap) or less than or equal to (in a Min-Heap) the values of its children.

How it Works:

When we traverse a heap in level order (starting from the top and going from left to right), we get the same order in which elements are arranged in an array.
The height of a node in a heap is the number of steps (or edges) it takes to reach the furthest leaf node from that node.
The height of the whole heap is determined by the height of its root node. Since a heap is a complete binary tree, its height is usually O(log n), where n is the number of elements in the heap. For example, in above tree, there are 7 nodes, so the height will be loge7≈1.9459.

Time Complexity:

Because of its structure, the basic operations like insertion, deletion, or finding the maximum or minimum element in a heap, usually take time proportional to the height of the tree.
In the worst-case scenario, these operations take O(log n) time, where n is the number of elements in the heap. This is because the height of the tree is logarithmic with respect to the number of elements.

Array Representation of a Heap:

You can represent a binary heap using an array. Here's how it works:

The root of the binary heap is stored at index 0 of the array.
If you have an element at index i in the array:
- Its left child is at index 2i + 1.
- Its right child is at index 2i + 2.
If you have an element at index i and it's not the root (i.e., i > 0), its parent is at index (i - 1) / 2.

Explanation:

You start with the root element at index 0.
For any element at index i, its children are at indices 2i + 1 (left child) and 2i + 2 (right child).
To find the parent of an element at index i (assuming it's not the root), you calculate (i - 1) / 2.

Example:

Let's say you have a heap array A with elements [10, 20, 30, 40, 50, 60, 70].

The root element (10) is at index 0.
The left child of 10 (20) is at index 2 * 0 + 1 = 1.
The right child of 10 (30) is at index 2 * 0 + 2 = 2.
The left child of 20 (40) is at index 2 * 1 + 1 = 3.
The right child of 20 (50) is at index 2 * 1 + 2 = 4.
And so on.

This representation helps in efficiently navigating and manipulating the heap structure using array operations.

Insertion: Add the new element at the end of the tree (the last position), then "bubble up" to maintain the heap property.
Deletion (specifically, deleting the root, which is the minimum element in a Min-Heap): Replace the root with the last element, remove the last element, then "bubble down" to maintain the heap property.

class MinHeap {
  constructor() {
    this.heap = []; // Initialize an empty array to store heap elements
  }

  // Get the index of the parent of the element at the given index
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // Get the index of the left child of the element at the given index
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  // Get the index of the right child of the element at the given index
  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  // Move the element at the given index up to its correct position to maintain the heap property
  bubbleUp(index) {
    let parentIndex = this.getParentIndex(index);
    // Continue to swap the element with its parent until the heap property is restored
    while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex; // Update index to the parent's index
      parentIndex = this.getParentIndex(index); // Get new parent index
    }
  }

  // Move the element at the given index down to its correct position to maintain the heap property
  bubbleDown(index) {
    let leftChildIndex = this.getLeftChildIndex(index);
    let rightChildIndex = this.getRightChildIndex(index);
    let smallest = index; // Assume the current index has the smallest value

    // Check if the left child exists and is smaller than the current smallest element
    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallest]) {
      smallest = leftChildIndex; // Update smallest to left child index
    }

    // Check if the right child exists and is smaller than the current smallest element
    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallest]) {
      smallest = rightChildIndex; // Update smallest to right child index
    }

    // If the smallest element is not the current element, swap and continue to bubble down
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.bubbleDown(smallest); // Recursively bubble down the swapped element
    }
  }

  // Insert a new value into the heap
  insert(value) {
    this.heap.push(value); // Add the new value to the end of the heap
    this.bubbleUp(this.heap.length - 1); // Restore the heap property by bubbling up
  }

  // Extract the minimum value from the heap
  extractMin() {
    if (this.heap.length === 0) {
      return null; // If the heap is empty, return null
    }
    if (this.heap.length === 1) {
      return this.heap.pop(); // If the heap has only one element, remove and return it
    }

    const min = this.heap[0]; // The root of the heap is the minimum element
    this.heap[0] = this.heap.pop(); // Move the last element to the root
    this.bubbleDown(0); // Restore the heap property by bubbling down
    return min; // Return the extracted minimum value
  }
}


// Example usage
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(30);
minHeap.insert(5);
minHeap.insert(15);

console.log(minHeap.extractMin()); // Outputs: 5
console.log(minHeap.extractMin()); // Outputs: 10

In the extractMin function, moving the last element to the root after removing the minimum element (the root) is a crucial step to maintain the heap structure. Here’s a detailed explanation of why this step is necessary:

Maintaining the Heap Structure

A heap is a complete binary tree, which means all levels are fully filled except possibly the last level, which is filled from left to right. When we remove the root element, the tree structure becomes incomplete. To maintain the completeness of the binary tree, we need to fill the gap created at the root.

Steps inextractMin

Extract the Minimum Element:
```
 const min = this.heap[0];
```
The minimum element in a min-heap is always at the root, this.heap[0].
Replace the Root with the Last Element:
```
 this.heap[0] = this.heap.pop();
```
- this.heap.pop() removes the last element of the heap and returns it.
- We assign this last element to the root position (this.heap[0]).

This step is necessary to maintain the completeness of the binary tree. By moving the last element to the root, we ensure that the tree remains complete, but it may violate the heap property (i.e., the new root might be larger than its children).

Restore the Heap Property:
```
 this.bubbleDown(0);
```
After moving the last element to the root, we need to restore the heap property. This is done by calling bubbleDown(0), which ensures that the new root element is moved to its correct position, maintaining the min-heap property (i.e., every parent node is smaller than its children).

Why Not Other Elements?

Completeness of the Binary Tree: Only the last element ensures that the tree remains complete when moved to the root. Any other element would leave a gap, breaking the structure of the complete binary tree.
Efficiency: Moving the last element to the root and then bubbling down is an efficient way to restore the heap property. It ensures that we perform a minimal number of operations to maintain both the structure and the heap property.

Visual Example

Consider a min-heap represented as an array: [1, 3, 2, 6, 5, 4].

Initial State:

Extract Min (1):
- Remove the root (1).
- Move the last element (4) to the root.

Bubble Down:
- Compare 4 with its children (3 and 2).
- Swap with the smallest child (2).

4 is now in the correct position, and the heap property is restored.

In summary, moving the last element to the root and then using bubbleDown is essential for maintaining the complete binary tree structure and efficiently restoring the heap property after extracting the minimum element.

Usage of`bubbleUp`:

The bubbleUp method is another fundamental operation in heap data structures, typically used when adding a new element to the heap. This method helps maintain the heap property by moving the newly added element up the heap until the correct position is found.

In a binary heap, every parent node must follow a specific ordering property relative to its children. For a max-heap, each parent node's value must be greater than or equal to its children's values. For a min-heap, each parent node's value must be less than or equal to its children's values.

When we add a new element to a heap, it's initially placed at the end of the heap. This placement might disrupt the heap property, so the bubbleUp (also known as siftUp or percolateUp) method is used to restore the heap property by repeatedly swapping the new element with its parent until the heap property is restored.

Approach :

Add the new element to the end of the heap.
Compare the element with its parent.
Swap it with the parent if necessary.
Repeat until the heap property is restored.

Usage of`bubbleDown`:

The bubbleDown method is an important operation in heap data structures, typically used in binary heaps to maintain the heap property after removing the root element (in a max-heap) or the smallest element (in a min-heap).

When we remove the root element from a heap, the last element in the heap is moved to the root position. This disrupts the heap property, and the bubbleDown (also known as heapify or siftDown) method is used to restore the heap property by repeatedly swapping the element with its largest (in max-heap) or smallest (in min-heap) child until the heap property is restored.

Approach :

Move the last element to the root position.
Compare the element with its children.
Swap it with the larger child (max-heap) or smaller child (min-heap).
Repeat until the heap property is restored.

Summary:

BubbleUp is used after inserting a new element to ensure it's in the correct place, moving up the tree if needed.
BubbleDown is used after removing the top element to fill the gap, moving down the tree if needed to maintain the heap property.

Both functions play crucial roles in maintaining the integrity of the heap data structure, ensuring efficient operations like insertion and extraction.

Heap Introduction

Usage ofbubbleUp:

Usage ofbubbleDown:

Summary:

Usage of`bubbleUp`:

Usage of`bubbleDown`: