Lecture 188:-Heaps Class - 3

Of course! Let's continue enhancing our Heap class by adding more functionalities such as peeking at the top element without removal and efficiently merging heaps. We'll also implement a heap sort algorithm using a Max Heap.

Here's the next part of the Heap class, including heap merging and heap sort:

pythonCopy code

class MaxHeap: # ... (previous code) def merge(self, other_heap): self.heap.extend(other_heap.heap) self._heapify_up(len(self.heap) - 1) def heap_sort(arr): max_heap = MaxHeap() max_heap.build_heap(arr) sorted_array = [] while not max_heap.is_empty(): sorted_array.append(max_heap.extract_max()) return sorted_array # Example usage max_heap1 = MaxHeap() max_heap1.build_heap([5, 10, 3, 8, 2]) max_heap2 = MaxHeap() max_heap2.build_heap([15, 12, 7, 6]) max_heap1.merge(max_heap2) print("Merged Max Heap:", max_heap1.heap) unsorted_array = [10, 3, 7, 1, 8, 4, 2, 5] sorted_array = heap_sort(unsorted_array) print("Sorted Array using Heap Sort:", sorted_array)

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

Merge Heaps: The merge method allows you to merge two heaps efficiently. It extends the current heap with the elements of another heap and then applies the _heapify_up operation to maintain the max heap property.

Heap Sort: The heap_sort function performs heap sort using a Max Heap. It builds a Max Heap from the given array, and then repeatedly extracts the maximum element from the heap to create a sorted array.

The example usage section demonstrates how to use the merge method to merge two heaps and how to perform heap sort using a Max Heap.

These additions provide a more versatile Heap class, allowing you to merge heaps and use heap sort for efficient sorting of arrays. Keep in mind that heaps are commonly used in various algorithms and data structures to maintain order and prioritize elements.