Lecture 186:-Heaps Class - 1

Sure! Let's start by implementing a basic Max Heap class in Python. A max heap is a binary tree where the value of each node is greater than or equal to the values of its children nodes. It has the property that the maximum value is always at the root.

Here's a simple implementation of a Max Heap class:

pythonCopy code

class MaxHeap: 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_max(self): if not self.heap: return None if len(self.heap) == 1: return self.heap.pop() max_value = self.heap[0] self.heap[0] = self.heap.pop() self._heapify_down(0) return max_value def _heapify_down(self, index): left_child = 2 * index + 1 right_child = 2 * index + 2 largest = index if left_child < len(self.heap) and self.heap[left_child] > self.heap[largest]: largest = left_child if right_child < len(self.heap) and self.heap[right_child] > self.heap[largest]: largest = right_child if largest != index: self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index] self._heapify_down(largest) # Example usage max_heap = MaxHeap() max_heap.insert(5) max_heap.insert(10) max_heap.insert(3) max_heap.insert(8) max_heap.insert(2) print("Max Heap:", max_heap.heap) print("Extracted Max Value:", max_heap.extract_max()) print("Max Heap after extraction:", max_heap.heap)

In this implementation, we've defined a MaxHeap class with methods to insert elements and extract the maximum value from the heap. The _heapify_up and _heapify_down methods are used to maintain the max heap property after insertion and extraction operations.

The insert method adds an element to the heap and then performs the _heapify_up operation to ensure the max heap property is maintained.

The extract_max method removes and returns the maximum value from the heap, replacing the root with the last element and then performing the _heapify_down operation to restore the max heap property.

This is a basic implementation of a Max Heap class. You can further extend it to include more functionalities like deleting specific elements, merging heaps, and building heaps from an array of elements.