Min heap

What is min-heap example? A Min-Heap is a complete binary Tree in which the value in each internal node is smaller than or equal to the values in the children of that node. Mapping the elements of a heap into an array is trivial: if a node is stored an index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.

• Node at 2, then left child at 5 and right at 6.
• Node at 1, left child 3 and right child at 4.

Explanation

• sift_up andsift_down are getting used below, replacing sift withheapify
• There is an empty Heap array
• What will be thetime_complexity ofsift_up ?
• Basicallysift_up is going to switch elements.
• If yousift_up then it is a small operation since only the condition that needs ✨

Python

class MinHeap:
    def __init__(self):
        self.heap = []
 
    def push(self, item):
        self.heap.append(item)
        self._heapify_up(len(self.heap) - 1)
 
    def pop(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root
 
    def peek(self):
        if self.heap:
            return self.heap[0]
 
    def _heapify_up(self, index):
        while index > 0:
            parent_index = (index - 1) // 2
            if self.heap[index] < self.heap[parent_index]:
                self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
                index = parent_index
            else:
                break
 
    def _heapify_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        smallest = index
 
        if (
            left_child_index < len(self.heap)
            and self.heap[left_child_index] < self.heap[smallest]
        ):
            smallest = left_child_index
 
        if (
            right_child_index < len(self.heap)
            and self.heap[right_child_index] < self.heap[smallest]
        ):
            smallest = right_child_index
 
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)
 
    def size(self):
        return len(self.heap)
 
    def is_empty(self):
        return len(self.heap) == 0

Javascript

• What do CLRS book say about heaps and do it mentionsift_up andsift_down

class MinHeap {
  constructor() {
    this.heap = [];
  }
 
  // Helper function to swap two elements in the heap
  swap(index1, index2) {
  [this.heap[index1], this.heap[index2]] = [this.heap[index2],
    this.heap[index1]]
  }
 
  // Sift up the element at the given index to maintain the min heap property
  siftUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
 
      if (this.heap[index] < this.heap[parentIndex]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }
 
  // Sift down the element at the given index to maintain the min heap property
  siftDown(index) {
    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.swap(index, smallestIndex);
      this.siftDown(smallestIndex);
    }
  }
 
  // Function to insert a value into the heap
  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
  }
 
  // Function to remove and return the minimum element from the heap
  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
 
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
 
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return minValue;
  }
 
  // Function to peek at the minimum element without removing it
  peekMin() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }
}
 
// Example usage:
const minHeap = new MinHeap();
minHeap.insert(4);
minHeap.insert(2);
minHeap.insert(9);
minHeap.insert(1);
 
console.log(minHeap.extractMin()); // Output: 1
console.log(minHeap.peekMin());    // Output: 2
 

Min heap accessing kth element

In a min-heap or max-heap, you can easily access the minimum or maximum element, respectively, which is the element at the root of the heap. However, accessing the second or third smallest (for a min-heap) or largest (for a max-heap) elements is not as straightforward.

If you want to access the second or third smallest elements in a min-heap, you would typically need to remove the minimum element from the heap (which would be the root) and then access the new root (which will now be the new minimum). You can repeat this process to access the second and third smallest elements. However, keep in mind that removing elements from the heap will affect its structure and might require reorganising the heap (heapify) after each removal.

If you need to access multiple smallest elements efficiently and repeatedly, you might consider using a data structure like a priority queue or a min-heap implemented with additional bookkeeping to track the second or third smallest elements. This approach would allow you to access these elements without the need for repeated removal and re-heapifying.