Heap Operations (Insert, Extract-Min/Max, Heapify)

Heap Operations: Insert, Extract-Min/Max, and Heapify

Heaps are highly efficient for operations that involve finding and removing the extreme element (minimum or maximum). The core operations that enable this efficiency are insert, extract-min (for min-heaps) or extract-max (for max-heaps), and heapify. These operations rely on maintaining the heap property through "sifting up" and "sifting down" elements.

---

1. Basic Heap Structure (Array-based Min-Heap)

As discussed, heaps are typically implemented using an array due to their complete binary tree nature. Let's consider a MinHeap implementation as an example.

class MinHeap {
  constructor(items = []) {
    this.heap = []; // The array representing the heap
    if (items.length > 0) {
      this.heap = items.slice(); // Copy items
      this.buildHeap(); // Build heap from initial items
    }
  }

  // Helper methods for navigating the array-based heap
  getParentIndex(i) { return Math.floor((i - 1) / 2); }
  getLeftChildIndex(i) { return 2 * i + 1; }
  getRightChildIndex(i) { return 2 * i + 2; }

  hasParent(i) { return this.getParentIndex(i) >= 0; }
  hasLeftChild(i) { return this.getLeftChildIndex(i) < this.heap.length; }
  hasRightChild(i) { return this.getRightChildIndex(i) < this.heap.length; }

  getParent(i) { return this.heap[this.getParentIndex(i)]; }
  getLeftChild(i) { return this.heap[this.getLeftChildIndex(i)]; }
  getRightChild(i) { return this.heap[this.getRightChildIndex(i)]; }

  swap(indexOne, indexTwo) {
    [this.heap[indexOne], this.heap[indexTwo]] = [this.heap[indexTwo], this.heap[indexOne]];
  }

  size() { return this.heap.length; }
  peek() {
    if (this.heap.length === 0) return undefined;
    return this.heap[0]; // The minimum element is always at the root
  }
}

---

2. Insert Operation (push)

To insert a new element into a min-heap:

1. Add the new element to the end of the array (maintaining completeness).
2. Sift Up (Heapify Up): Compare the new element with its parent. If it's smaller, swap them. Continue this process, moving the element up the tree, until it's greater than or equal to its parent, or it becomes the root.

• Pseudocode (siftUp method for MinHeap):

  // Inside MinHeap class
  siftUp(index) {
    while (this.hasParent(index) && this.getParent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index);
    }
  }
  
  push(item) {
    this.heap.push(item);
    this.siftUp(this.heap.length - 1); // Sift up the newly added item
  }
  

• Time Complexity: O(log N) because, in the worst case, the element might travel from the leaf to the root, which is proportional to the height of the tree.

---

3. Extract-Min/Max Operation (pop)

To remove the minimum element from a min-heap (or maximum from a max-heap):

1. The minimum element is always at the root (index 0). Store it to return later.
2. Move the last element of the heap (from the end of the array) to the root position.
3. Remove the last element from the array (reducing size).
4. Sift Down (Heapify Down): Compare the new root with its children. If it's larger than either child (in a min-heap), swap it with the smaller of its children. Continue this process, moving the element down the tree, until it's smaller than or equal to both children, or it becomes a leaf.

• Pseudocode (siftDown and pop methods for MinHeap):

  // Inside MinHeap class
  siftDown(index) {
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      if (this.hasRightChild(index) && this.getRightChild(index) < this.getLeftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
  
      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break; // Heap property is satisfied
      } else {
        this.swap(index, smallerChildIndex);
      }
      index = smallerChildIndex;
    }
  }
  
  pop() { // Extracts the minimum element
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop(); // Only one element, just remove it
  
    const item = this.heap[0]; // The minimum item
    this.heap[0] = this.heap.pop(); // Move last item to root
    this.siftDown(0); // Sift down the new root
    return item;
  }
  

• Time Complexity: O(log N) because, in the worst case, the element might travel from the root to a leaf, proportional to the height of the tree.

---

4. Build Heap (buildHeap)

To convert an arbitrary array into a heap:

1. Start from the last non-leaf node (which is Math.floor(N/2) - 1 for a 0-indexed array of size N).
2. Perform siftDown on this node.
3. Move backwards towards the root (index 0), performing siftDown on each node.

• Pseudocode (buildHeap method for MinHeap):

  // Inside MinHeap class
  buildHeap() {
    // Start from the last non-leaf node and go up to the root
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.siftDown(i);
    }
  }
  

• Time Complexity: O(N). Although siftDown is O(log N), the majority of siftDown calls are on nodes near the leaves (where the height is small), leading to an overall O(N) complexity for building the heap.

---

Key Takeaway: Heap operations (insert, pop, buildHeap) are efficient due to the heap's complete binary tree structure and the siftUp/siftDown mechanisms that maintain the heap property. These operations provide logarithmic time complexity, making heaps a powerful tool for priority management.