Binomial Heap

Binomial Heap is a data structure that combines the advantages of both binary heap and linked list. It is used to efficiently support operations like insertion, deletion, and merging of heaps. Each Binomial Heap is composed of multiple Binomial Trees, which are defined recursively.

In a Binomial Tree of order k, there are k children rooted at the root node. The order of the tree corresponds to the number of children it has. The unique property of Binomial Heap is that the root of each tree in the heap has a key greater than or equal to the keys of its children, making it suitable for priority queue applications.

Let's implement a Binomial Heap in Python:

class BinomialNode:
    def __init__(self, value):
        self.value = value
        self.order = 0
        self.child = None
        self.sibling = None


class BinomialHeap:
    def __init__(self):
        self.head = None

    def merge(self, heap):
        new_heap = BinomialHeap()
        new_heap.head = self.merge_trees(self.head, heap.head)
        self.head = None
        heap.head = None
        return new_heap

    def merge_trees(self, tree1, tree2):
        if tree1 is None:
            return tree2
        if tree2 is None:
            return tree1
        if tree1.value < tree2.value:
            tree1.child = self.merge_trees(tree1.child, tree2)
            tree1.order += 1
            return tree1
        else:
            tree2.child = self.merge_trees(tree2.child, tree1)
            tree2.order += 1
            return tree2

    def insert(self, value):
        heap = BinomialHeap()
        heap.head = BinomialNode(value)
        self.head = self.merge(heap).head

    def find_min(self):
        if self.head is None:
            return None
        min_node = self.head
        current = self.head
        while current.sibling is not None:
            if current.sibling.value < min_node.value:
                min_node = current.sibling
            current = current.sibling
        return min_node.value

    def extract_min(self):
        if self.head is None:
            return None
        min_node = self.head
        prev_min_node = None
        current = self.head
        while current.sibling is not None:
            if current.sibling.value < min_node.value:
                min_node = current.sibling
                prev_min_node = current
            current = current.sibling

        if prev_min_node is None:
            self.head = min_node.child
        else:
            prev_min_node.sibling = min_node.sibling

        new_heap = BinomialHeap()
        new_heap.head = self.reverse_children(min_node.child)
        self.head = self.merge(new_heap).head

        return min_node.value

    def reverse_children(self, node):
        if node is None or node.sibling is None:
            return node

        reversed_child = self.reverse_children(node.sibling)
        node.sibling.sibling = node
        node.sibling = None
        return reversed_child

Now, let's solve a LeetCode problem using the Binomial Heap we implemented. The problem is "Find Median from Data Stream," where we need to design a data structure that supports adding numbers and finding the median of all elements seen so far efficiently.

class MedianFinder:
    def __init__(self):
        self.max_heap = BinomialHeap()
        self.min_heap = BinomialHeap()

    def addNum(self, num):
        if self.max_heap.find_min() is None or num < self.max_heap.find_min():
            self.max_heap.insert(num)
        else:
            self.min_heap.insert(num)

        if self.max_heap.head is not None and self.min_heap.head is not None:
            if self.max_heap.head.order > self.min_heap.head.order:
                self.max_heap, self.min_heap = self.min_heap, self.max_heap

        while (
            self.max_heap.head is not None
            and self.min_heap.head is not None
            and self.max_heap.head.order == self.min_heap.head.order
        ):
            self.max_heap_child = self.max_heap.extract_min()
            self.min_heap_child = self.min_heap.extract_min()
            self.max_heap.insert(self.max_heap_child)
            self.max_heap.insert(self.min_heap_child)

    def findMedian(self):
        if self.max_heap.head is None and self.min_heap.head is None:
            return None

        if self.max_heap.head.order > self.min_heap.head.order:
            return float(self.max_heap.find_min())

        median = (self.max_heap.find_min() + self.min_heap.find_min()) / 2
        return median

The MedianFinder class uses two Binomial Heaps, one for storing the smaller half of the numbers (max heap) and another for storing the larger half of the numbers (min heap). The addNum function inserts the number into the appropriate heap based on the current median. The findMedian function calculates the median by comparing the sizes of the two heaps and finding the middle element(s).

The time complexity of the addNum function is O(log n), where n is the total number of elements inserted. The findMedian function has a time complexity of O(1).