Min Heap

Let's dive into the implementation of a Min Heap in Python, explain each function, and solve a question from LeetCode using this concept.

class MinHeap:
    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)
        smallest = i

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

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

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

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

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

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

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

        return min_value

Now let's solve a question from LeetCode using a Min 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 = MinHeap()

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

    return heap.extract_min()

In this example, we create a MinHeap 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 minimum element from the heap to maintain the heap size as k. Finally, we return the minimum 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_min 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 min heap.