Max Heap

  Here's an explanation of the MaxHeap class, its functions, and an example of solving a question from LeetCode using a max heap.

class MaxHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def heapify_up(self, i):
        parent_idx = self.parent(i)
        if parent_idx >= 0 and self.heap[i] > self.heap[parent_idx]:
            self.swap(i, parent_idx)
            self.heapify_up(parent_idx)

    def heapify_down(self, i):
        left_child_idx = self.left_child(i)
        right_child_idx = self.right_child(i)
        largest = i

        if left_child_idx < len(self.heap) and self.heap[left_child_idx] > self.heap[largest]:
            largest = left_child_idx

        if right_child_idx < len(self.heap) and self.heap[right_child_idx] > self.heap[largest]:
            largest = right_child_idx

        if largest != i:
            self.swap(i, largest)
            self.heapify_down(largest)

    def insert(self, value):
        self.heap.append(value)
        index = len(self.heap) - 1
        self.heapify_up(index)

    def extract_max(self):
        if len(self.heap) == 0:
            return None

        max_value = self.heap[0]
        last_value = self.heap.pop()

        if len(self.heap) > 0:
            self.heap[0] = last_value
            self.heapify_down(0)

        return max_value

Let's solve a question from LeetCode using a max heap. Consider the problem "Kth Largest Element in an Array" (LeetCode #215), where we need to find the Kth largest element in an unsorted array. 

def find_kth_largest(nums, k):
    heap = MaxHeap()

    for num in nums:
        heap.insert(num)
        if len(heap.heap) > k:
            heap.extract_max()

    return heap.extract_max()

In this example, we create a MaxHeap object and iterate through the elements in the nums array. We insert each element into the heap, and if the size of the heap becomes larger than k, we extract the maximum element from the heap to maintain the heap size as k. Finally, we return the maximum element from the heap, which will be the Kth largest element in the array.

The time complexity of the find_kth_largest function is O(n * log k), where n is the size of the input array. The insert and extract_max operations in the heap both have a time complexity of O(log k), and we perform these operations for each element in the array. The space complexity is O(k) for storing the elements in the max heap.