Heap

A heap is a specialized tree-based data structure that satisfies the heap property. The heap property specifies that for a heap with a parent node and its children, the value of the parent node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values of its children.

Heaps are commonly used to implement priority queues, where elements with higher priorities are dequeued first. They provide efficient insertion, deletion, and retrieval of the highest-priority element.

In Python, the heapq module provides functions to work with heaps. However, I'll explain the heap concept and implement it from scratch without using any library.

Here's an example implementation of a min heap in Python:

class MinHeap:
    def __init__(self):
        self.heap = []
        self.size = 0

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

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

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

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

    def insert(self, value):
        self.heap.append(value)
        self.size += 1
        self.heapify_up(self.size - 1)

    def heapify_up(self, index):
        while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
            self.swap(index, self.parent(index))
            index = self.parent(index)

    def extract_min(self):
        if self.size == 0:
            return None
        minimum = self.heap[0]
        self.swap(0, self.size - 1)
        self.heap.pop()
        self.size -= 1
        self.heapify_down(0)
        return minimum

    def heapify_down(self, index):
        while True:
            left = self.left_child(index)
            right = self.right_child(index)
            smallest = index
            if left < self.size and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < self.size and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == index:
                break
            self.swap(index, smallest)
            index = smallest

Now, let's solve a LeetCode problem using the min heap we implemented. The problem is "Merge k Sorted Lists," where we need to merge k sorted linked lists into a single sorted list.

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


def merge_k_lists(lists):
    min_heap = MinHeap()
    # Insert the first node from each list into the min heap
    for head in lists:
        if head:
            min_heap.insert(head.val)

    # Create a dummy node to build the merged list
    dummy = ListNode(0)
    current = dummy

    # Process the nodes in ascending order using the min heap
    while min_heap.size > 0:
        min_val = min_heap.extract_min()
        current.next = ListNode(min_val)
        current = current.next

        # Find the next node in the list and insert its value into the min heap
        for head in lists:
            if head and head.val == min_val:
                head = head.next
                if head:
                    min_heap.insert(head.val)

    return dummy.next

The time complexity of the insert operation in the min heap is O(log n), where n is the number of elements in the heap. The extract_min operation also has a time complexity of O(log n). Since we insert all elements from the input lists into the heap, the overall time complexity of the merge_k_lists function is O(n log k), where n is the total number of elements across all lists and k is the number of lists.

The space complexity is O(k), as we only store the elements from the k input lists in the min heap.