Min Heap and Max Heap 🎯

Welcome to the exciting world of Data Structures and Algorithms! Today, we're going to delve into two essential concepts: Min Heap and Max Heap. These data structures are fundamental in computer science and are widely used in real-world projects.

Understanding Heaps 📝

A Heap is a specialized tree-based data structure, used for priority queue implementation. It has a unique property that the parent node is always greater than or less than its child nodes, depending on whether we're dealing with a Max Heap or Min Heap.

Min Heap 💡

A Min Heap is a heap where each node is greater than or equal to its children. The smallest element is at the root. Here's a simple example:

python

# Example Min Heap
data = [12, 25, 6, 32, 9, 50, 49]

def min_heapify(arr, n, i):
    # Complete the min_heapify function here
    pass

def build_min_heap(arr):
    # Complete the build_min_heap function here
    pass

data = build_min_heap(data)
print(data)  # Output: [6, 12, 25, 32, 9, 49, 50]

In this example, the smallest element is 6, and it's located at the root (index 0).

Building a Min Heap 📝

We can build a Min Heap using the build_min_heap function:

python

def build_min_heap(arr):
    n = len(arr)

    for i in range(n // 2, -1, -1):
        min_heapify(arr, n, i)

    return arr

Heapifying a Min Heap 💡

To maintain the Min Heap property, we use the min_heapify function:

python

def min_heapify(arr, n, i):
    smallest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] < arr[smallest]:
        smallest = l

    if r < n and arr[r] < arr[smallest]:
        smallest = r

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        min_heapify(arr, n, smallest)

Now that you understand Min Heaps, let's move on to Max Heaps!

Max Heap 💡

A Max Heap is a heap where each node is smaller than or equal to its children. The largest element is at the root. Here's an example:

python

# Example Max Heap
data = [12, 25, 6, 32, 9, 50, 49]

def max_heapify(arr, n, i):
    # Complete the max_heapify function here
    pass

def build_max_heap(arr):
    # Complete the build_max_heap function here
    pass

data = build_max_heap(data)
print(data)  # Output: [49, 50, 25, 32, 12, 9, 6]

In this example, the largest element is 49, and it's located at the root (index 0).

Building a Max Heap 📝

Similar to Min Heap, we can build a Max Heap using the build_max_heap function:

python

def build_max_heap(arr):
    n = len(arr)

    for i in range(n // 2, -1, -1):
        max_heapify(arr, n, i)

    return arr

Heapifying a Max Heap 💡

To maintain the Max Heap property, we use the max_heapify function:

python

def max_heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l

    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, n, largest)

Now that you've learned about Min Heaps and Max Heaps, you're one step closer to mastering Data Structures and Algorithms! Keep exploring and practicing to improve your skills. Happy coding! 🚀✨