Randomized Heap

Randomized Heap is a variation of the heap data structure where the elements are stored in a binary tree-like structure. In addition to the properties of a regular heap, a Randomized Heap also maintains a random priority for each element, which determines their position in the heap.

The Randomized Heap supports the following operations:

• insert(value): Inserts a new element with the given value into the heap.
• delete(value): Deletes the element with the given value from the heap.
• find_min(): Returns the minimum element in the heap.
• extract_min(): Removes and returns the minimum element from the heap.
• merge(heap): Merges the current heap with another heap, combining their elements.
• is_empty(): Checks if the heap is empty.

To implement a Randomized Heap in Python, we can define a RandomizedHeap class and its associated functions.

import random

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

    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)

    def delete(self, value):
        if value in self.heap:
            index = self.heap.index(value)
            self._swap(index, len(self.heap) - 1)
            self.heap.pop()
            self._bubble_down(index)

    def find_min(self):
        if self.heap:
            return self.heap[0]
        return None

    def extract_min(self):
        if self.heap:
            self._swap(0, len(self.heap) - 1)
            min_val = self.heap.pop()
            self._bubble_down(0)
            return min_val
        return None

    def merge(self, heap):
        self.heap += heap.heap
        self._build_heap()

    def is_empty(self):
        return len(self.heap) == 0

    def _bubble_up(self, index):
        parent_idx = (index - 1) // 2
        while index > 0 and self.heap[index] < self.heap[parent_idx]:
            self._swap(index, parent_idx)
            index = parent_idx
            parent_idx = (index - 1) // 2

    def _bubble_down(self, index):
        left_child_idx = 2 * index + 1
        right_child_idx = 2 * index + 2

        while left_child_idx < len(self.heap):
            smallest_child_idx = left_child_idx

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

            if self.heap[index] <= self.heap[smallest_child_idx]:
                break

            self._swap(index, smallest_child_idx)
            index = smallest_child_idx
            left_child_idx = 2 * index + 1
            right_child_idx = 2 * index + 2

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

    def _build_heap(self):
        n = len(self.heap)
        for i in range(n // 2 - 1, -1, -1):
            self._bubble_down(i)

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

    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 RandomizedHeap 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 Randomized Heap.