Lecture 187:-Heaps Class - 2

Certainly! Let's continue enhancing our Max Heap class by adding more functionalities such as building a heap from an array and checking if the heap is empty. Additionally, we'll implement a Min Heap class as well.

Here's the next part of the Heap class, including a Min Heap implementation:

pythonCopy code

class MaxHeap: def __init__(self): self.heap = [] # ... (previous code) def build_heap(self, arr): self.heap = arr for i in range(len(arr) // 2 - 1, -1, -1): self._heapify_down(i) def is_empty(self): return len(self.heap) == 0 class MinHeap: def __init__(self): self.heap = [] def insert(self, value): self.heap.append(value) self._heapify_up(len(self.heap) - 1) def _heapify_up(self, index): parent = (index - 1) // 2 while index > 0 and self.heap[index] < self.heap[parent]: self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index] index = parent parent = (index - 1) // 2 def extract_min(self): if not self.heap: return None if len(self.heap) == 1: return self.heap.pop() min_value = self.heap[0] self.heap[0] = self.heap.pop() self._heapify_down(0) return min_value def _heapify_down(self, index): left_child = 2 * index + 1 right_child = 2 * index + 2 smallest = index if left_child < len(self.heap) and self.heap[left_child] < self.heap[smallest]: smallest = left_child if right_child < len(self.heap) and self.heap[right_child] < self.heap[smallest]: smallest = right_child if smallest != index: self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index] self._heapify_down(smallest) # ... (build_heap and is_empty methods can be added similar to MaxHeap) # Example usage max_heap = MaxHeap() max_heap.build_heap([5, 10, 3, 8, 2]) print("Max Heap after building:", max_heap.heap) min_heap = MinHeap() min_heap.insert(5) min_heap.insert(10) min_heap.insert(3) min_heap.insert(8) min_heap.insert(2) print("Min Heap:", min_heap.heap) print("Extracted Min Value:", min_heap.extract_min()) print("Min Heap after extraction:", min_heap.heap)

In this part, we've added the following functionalities to the Heap class:

Build Heap: The build_heap method constructs a heap from a given array. It starts from the last non-leaf node and performs the _heapify_down operation for each node to establish the heap property.

Is Empty: The is_empty method checks whether the heap is empty or not.

We've also introduced a MinHeap class, which is similar to the MaxHeap class but maintains the min heap property where each node's value is less than or equal to the values of its children nodes.

These additions provide a more comprehensive Heap class, allowing you to work with both max heaps and min heaps and perform operations such as building heaps from arrays and checking for emptiness.