Skew Heap

 Skew Heap, also known as Self-Adjusting Heaps, is a type of binary heap that allows efficient merge and delete operations in addition to the usual heap operations like insertion and extraction of the minimum element.

Skew Heap is implemented using a binary tree structure where each node has a key and two children, left and right. The key property of the Skew Heap is that the value in the left child should always be greater than or equal to the value in the right child. This property is called the "skew" property.

The Skew Heap supports the following operations:

• merge(heap1, heap2): Merges two Skew Heaps heap1 and heap2 into a single heap.
• insert(value): Inserts a new element with the given value into the heap.
• extract_min(): Removes and returns the minimum element from the heap.
• is_empty(): Checks if the heap is empty.

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

class SkewHeapNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class SkewHeap:
    def __init__(self):
        self.root = None

    def merge(self, heap1, heap2):
        if heap1 is None:
            return heap2
        if heap2 is None:
            return heap1

        if heap1.value > heap2.value:
            heap1, heap2 = heap2, heap1

        heap1.right = self.merge(heap1.right, heap2)
        heap1.left, heap1.right = heap1.right, heap1.left

        return heap1

    def insert(self, value):
        node = SkewHeapNode(value)
        self.root = self.merge(self.root, node)

    def extract_min(self):
        if self.is_empty():
            return None

        min_val = self.root.value
        self.root = self.merge(self.root.left, self.root.right)

        return min_val

    def is_empty(self):
        return self.root is None

Now let's solve a question from LeetCode using the Skew Heap. Consider the problem "Merge k Sorted Lists" (LeetCode #23), where we need to merge k sorted linked lists into one sorted list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    heap = SkewHeap()
    
    # Insert the head nodes of all lists into the heap
    for head in lists:
        if head:
            heap.insert(head)
    
    # Create a dummy node to build the merged list
    dummy = ListNode(0)
    curr = dummy
    
    # Merge the lists by extracting the minimum nodes from the heap
    while not heap.is_empty():
        min_node = heap.extract_min()
        
        # Append the minimum node to the merged list
        curr.next = min_node
        curr = curr.next
        
        # Move to the next node in the list
        if min_node.next:
            heap.insert(min_node.next)
    
    return dummy.next

In this example, we create a SkewHeap object and insert the head nodes of all the linked lists into the heap. We then create a dummy node to build the merged list, and in each iteration, we extract the minimum node from the heap and append it to the merged list. We also insert the next node of the extracted node back into the heap if it exists. Finally, we return the merged list.

The time complexity of the merge_k_lists function is O(N log K), where N is the total number of nodes in all the linked lists and K is the number of linked lists. The insert and extract_min operations in the Skew Heap both have a time complexity of O(log K), and we perform these operations for each node in the linked lists. The space complexity is O(K) for storing the nodes in the Skew Heap.