Min Heap

How Min Heap Works

A Min Heap is a complete binary tree where the parent node is always smaller than or equal to its children. The root of the tree is always the minimum element in the heap.

Key operations:

• Insert: O(log n) - Add an element to the end and bubble up
• Extract Min: O(log n) - Remove the root, replace with last element, and bubble down
• Peek Min: O(1) - Return the root element without removing it

Min Heaps are commonly used in priority queues, scheduling algorithms, and in algorithms like Dijkstra's shortest path and Prim's minimum spanning tree.

class MinHeap:
    heap

    function insert(value):
        heap.append(value)
        heapifyUp(heap.length - 1)
        visualize()

    function extractMin():
        if heap is empty:
            return null
        min = heap[0]
        lastElement = heap.pop()
        if heap is not empty:
            heap[0] = lastElement
            heapifyDown(0)
        visualize()
        return min

    function heapifyUp(index):
        while index > 0 and heap[parent(index)] > heap[index]:
            swap heap[parent(index)] and heap[index]
            index = parent(index)

    function heapifyDown(index):
        minIndex = index
        left = leftChild(index)
        right = rightChild(index)
        if left < heap.length and heap[left] < heap[minIndex]:
            minIndex = left
        if right < heap.length and heap[right] < heap[minIndex]:
            minIndex = right
        if minIndex != index:
            swap heap[index] and heap[minIndex]
            heapifyDown(minIndex)

    function parent(i): return (i - 1) / 2
    function leftChild(i): return 2 * i + 1
    function rightChild(i): return 2 * i + 2