Heap Generic

 

Heap is a data structure that allows efficient access to the minimum (or maximum) element in a collection. It is commonly used to implement priority queues and sorting algorithms. In a generic heap, elements can be of any type, as long as a comparison function is provided to determine their relative ordering.

Let's implement a generic heap in Python using a min-heap as an example:


class Heap:
    def __init__(self, comparison_fn):
        self.heap = []
        self.comparison_fn = comparison_fn

    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):
        while i > 0 and self.comparison_fn(self.heap[i], self.heap[self.parent(i)]):
            parent = self.parent(i)
            self.swap(i, parent)
            i = parent

    def heapify_down(self, i):
        size = len(self.heap)
        while True:
            smallest = i
            left = self.left_child(i)
            right = self.right_child(i)

            if left < size and self.comparison_fn(self.heap[left], self.heap[smallest]):
                smallest = left

            if right < size and self.comparison_fn(self.heap[right], self.heap[smallest]):
                smallest = right

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

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

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

        min_value = self.heap[0]
        self.swap(0, len(self.heap) - 1)
        self.heap.pop()
        self.heapify_down(0)

        return min_value

Now, let's solve a LeetCode problem using the generic heap we implemented. The problem is "Kth Smallest Element in a Sorted Matrix," where we are given a matrix with each row and column sorted in ascending order, and we need to find the kth smallest element in the matrix.


def kthSmallest(matrix, k):
    heap = Heap(lambda x, y: x[0] < y[0])
    rows = len(matrix)
    cols = len(matrix[0])

    # Insert the first element from each row into the heap
    for i in range(rows):
        heap.insert((matrix[i][0], i, 0))

    # Extract the minimum element k times
    for _ in range(k - 1):
        value, row, col = heap.extract_min()

        # If the current element has a next element in its row, insert it into the heap
        if col + 1 < cols:
            heap.insert((matrix[row][col + 1], row, col + 1))

    # The kth smallest element is the minimum element in the heap
    return heap.extract_min()[0]

In this solution, we use the generic Heap class to maintain a min-heap of tuples (value, row, col). We initially insert the first element from each row into the heap. Then, we iteratively extract the minimum element k - 1 times and insert the next element from the same row if it exists. Finally, we extract the minimum element, which gives us the kth smallest element in the matrix.

The time complexity of this solution is O(k log r), where r is the number of rows in the matrix. Since k is typically much smaller than the total number of elements in the matrix, this solution is efficient. The space complexity is O(r), as we only store at most one element from each row in the heap.

 Here's an explanation of each function in the Heap class for a min-heap:

  1. __init__(self, comparison_fn): This is the constructor of the Heap class. It initializes the heap list as an empty list and takes a comparison_fn parameter, which is a function that compares two elements and returns True if the first element is smaller than the second element. This function is used to determine the ordering of the elements in the heap.

  2. parent(self, i): This function returns the index of the parent node given the index i of a node.

  3. left_child(self, i): This function returns the index of the left child node given the index i of a node.

  4. right_child(self, i): This function returns the index of the right child node given the index i of a node.

  5. swap(self, i, j): This function swaps the elements at indices i and j in the heap.

  6. heapify_up(self, i): This function performs the "heapify up" operation, which ensures that the element at index i satisfies the heap property. It compares the element with its parent and swaps them if necessary, repeatedly moving up the heap until the heap property is satisfied.

  7. heapify_down(self, i): This function performs the "heapify down" operation, which ensures that the element at index i satisfies the heap property. It compares the element with its children and swaps it with the smallest child if necessary, repeatedly moving down the heap until the heap property is satisfied.

  8. insert(self, value): This function inserts a new value into the heap. It appends the value to the end of the heap and then performs the heapify up operation to maintain the heap property.

  9. extract_min(self): This function extracts the minimum element from the heap, which is the root of the heap. It swaps the root with the last element in the heap, removes the last element, and then performs the heapify down operation to maintain the heap property.

These functions collectively provide the necessary operations to maintain a min-heap data structure. They ensure that the minimum element is always at the root of the heap and that inserting and extracting elements are done efficiently.

 

Next Post Previous Post