Min Heap Construction

A MinHeap is a binary tree-based data structure where the value of each node is less than or equal to the values of its children.

To successfully construct a Min heap, you will have to master the following methods:~

•  Build Heap
•  Sift Down
•  Sift Up
•  Insert
•  Remove

Problem

In this solution, I am solving the problem of implementing the functionality of a MinHeap, which allows for efficient insertion, removal of the minimum element (root), and maintaining the heap property.

class MinHeap:
    """
    A class representing a MinHeap data structure.

    Attributes:
        heap (list): The list representing the binary heap.
    """

    def __init__(self, array):
        """
        Initializes a MinHeap object with the given array.

        Args:
            array (list): The array to be converted into a MinHeap.
        """
        self.heap = self.build_heap(array)

    def build_heap(self, array):
        """
        Builds a MinHeap from the given array.

        Args:
            array (list): The array to be converted into a MinHeap.

        Returns:
            list: The array representing the MinHeap.
        """
        first_parent_idx = (len(array) - 2) // 2
        for current_idx in reversed(range(first_parent_idx)):
            self.sift_down(current_idx, len(array) - 1, array)
        return array

    def sift_down(self, current_idx, end_idx, heap):
        """
        Performs a sift down operation on the heap.

        Args:
            current_idx (int): The index of the current node.
            end_idx (int): The index of the last node in the heap.
            heap (list): The list representing the binary heap.
        """
        child_one_idx = current_idx * 2 + 1
        while child_one_idx <= end_idx:
            child_two_idx = current_idx * 2 + 2 if current_idx * 2 + 2 <= end_idx else -1
            if child_two_idx != -1 and heap[child_two_idx] < heap[child_one_idx]:
                idx_to_swap = child_two_idx
            else:
                idx_to_swap = child_one_idx
            if heap[idx_to_swap] < heap[current_idx]:
                self.swap(current_idx, idx_to_swap, heap)
                current_idx = idx_to_swap
                child_one_idx = current_idx * 2 + 1
            else:
                break

    def sift_up(self, current_idx, heap):
        """
        Performs a sift up operation on the heap.

        Args:
            current_idx (int): The index of the current node.
            heap (list): The list representing the binary heap.
        """
        parent_idx = (current_idx - 1) // 2
        while current_idx > 0 and heap[current_idx] < heap[parent_idx]:
            self.swap(current_idx, parent_idx, heap)
            current_idx = parent_idx
            parent_idx = (current_idx - 1) // 2

    def remove(self):
        """
        Removes and returns the minimum element from the heap.

        Returns:
            int: The minimum element removed from the heap.
        """
        self.swap(0, len(self.heap) - 1, self.heap)
        value_to_remove = self.heap.pop()
        self.sift_down(0, len(self.heap) - 1, self.heap)
        return value_to_remove

    def insert(self, value):
        """
        Inserts a new element into the heap.

        Args:
            value (int): The value to be inserted into the heap.
        """
        self.heap.append(value)
        self.sift_up(len(self.heap) - 1, self.heap)

    def swap(self, i, j, heap):
        """
        Swaps the elements at the given indices in the heap.

        Args:
            i (int): The index of the first element.
            j (int): The index of the second element.
            heap (list): The list representing the binary heap.
        """
        heap[i], heap[j] = heap[j], heap[i]

Approach

The solution uses the binary heap data structure to implement the MinHeap. Here's a brief overview of each method:

__init__ method

Initializes the MinHeap with an array of elements and builds the heap using the buildHeap method.

buildHeap

Builds the heap from an input array by repeatedly calling siftDown starting from the last parent node.

siftDown

Corrects a single violation of the heap property by swapping a node with its smaller child recursively until the heap property is restored.

siftUp

Continuously swaps the current node that we've inserted with its parent nodes until it's in its' correct position. By so doing, the heap property is restored.

remove

Removes and returns the minimum element from the heap (the root), and restores the heap property by calling siftDown.

insert

Inserts a new element into the heap, restores the heap property by calling siftUp.

swap

Swaps the elements at two given indices in the heap.

Time & Space Complexity

Let's analyze the time and space complexity of each method in the MinHeap class:

 __init__ method

The __init__ method calls the build_heap method, which has a time complexity of O(n), where n is the number of elements in the input array.

build_heap method

The build_heap method iterates through each node of the binary heap and calls the sift_down method for each node. Since the sift_down operation has a time complexity of O(log(n)), where n is the number of elements in the heap, the overall time complexity of build_heap is O(n *(log n)).

sift_down method

The sift_down method performs a series of comparisons and swaps while traversing down the heap, maintaining the heap property. In the worst case, it performs a logarithmic number of operations, so the time complexity is logarithmic i.e. Log N where N is the number of elements in the heap.

sift_up method

The sift_up method performs a series of comparisons and swaps while traversing up the heap, maintaining the heap property. In the worst case, it performs a logarithmic number of operations, so the time complexity is logarithmic i.e. Log N where N is the number of elements in the heap.

remove method

The remove method removes the minimum element from the heap and then performs a sift_down operation to maintain the heap property. Both removing the minimum element and performing sift_down have a time complexity of logarithmic i.e. Log N where N is the number of elements in the heap.

insert method

The insert method adds a new element to the heap and then performs a sift_up operation to maintain the heap property. Both adding the element and performing sift_up have a logarithmic time complexity i.e. Log N where N is the number of elements in the heap.

swap method

The swap method performs a constant number of operations, so the time complexity is O(1).

For all the methods above (swap, insert, remove, sift_up, sift_down, build_heap), the space Complexity is O(1) since no additional space is used.

Unit Tests

Below I explore unit tests using Python's unittest module to test the correctness and robustness of the MinHeap class:

These unit tests cover various scenarios:

Each test case asserts whether the MinHeap class behaves correctly for a given operation. These tests help ensure the correctness and robustness of the solution.

Use Cases

MinHeaps are commonly used in various scenarios such as:

•     Implementing priority queues.
•     Implementing algorithms like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm.
•     Efficiently finding the k smallest (or largest) elements in an array.

Application

The MinHeap data structure implemented by this solution can be used whenever we need to maintain a collection of elements with efficient insertion and removal of the minimum element.