C Min Heap 🎯

Welcome to our deep dive into the world of C Programming! Today, we're going to explore Min Heap, a fundamental data structure that plays a crucial role in algorithms and data management. Let's get started!

What is a Min Heap? 📝

A Min Heap is a special type of Heap where the root (top) element is always the minimum value among all the elements in the Heap. Sounds intriguing? Let's break it down.

Heap Overview 💡

A Heap is a complete binary tree (a tree where all levels, except possibly the last, are completely filled, and all nodes are as far left as possible). It has a unique property: the value of a parent node is greater than or equal to (for Max Heap) or less than or equal to (for Min Heap) the value of its children.

In this lesson, we will focus on Min Heap.

Min Heap Properties 📝

Min Heap Property: The minimum value is always at the root (top).
Complete Binary Tree: No empty slots at lower levels, all levels filled except possibly the last.
Heapify Property: For every node i, the value is less than or equal to its parent's value, i.e., heap[parent(i)] <= heap[i].

Min Heap Operations 📝

Insert: Add a new element to the Heap, maintaining the Min Heap Property.
Extract Min: Remove the minimum element from the Heap, while maintaining the Min Heap Property.
Heapify: Restore the Min Heap Property for a subtree rooted at an arbitrary node.

Building a Min Heap 💡

To build a Min Heap, we can use the heapify algorithm, which rearranges the elements in a complete binary tree to satisfy the Min Heap Property. Here's a simple step-by-step guide:

Start from the last parent node (the second node from the last level).
Compare the current node (i) and its parent (parent(i)).
If the Min Heap Property is violated, swap the values and proceed with the parent node.
Repeat until the root node is reached or the Min Heap Property is satisfied.

Coding Min Heap Operations ✅

Let's write a simple Min Heap implementation in C. We'll create functions for insert, extractMin, and heapify.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int heap[MAX];
int size = 0, capacity = MAX;

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int parent(int i) {
    return (i - 1) / 2;
}

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

void heapify(int i) {
    int l = left(i), r = right(i), smallest = i;

    if (l < size && heap[l] < heap[smallest])
        smallest = l;

    if (r < size && heap[r] < heap[smallest])
        smallest = r;

    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(smallest);
    }
}

void insert(int value) {
    if (size == capacity) {
        printf("Heap is full. Increase capacity.\n");
        return;
    }
    heap[size++] = value;
    int i = size - 1;
    while (i != 0 && heap[parent(i)] > heap[i]) {
        swap(&heap[i], &heap[parent(i)]);
        i = parent(i);
    }
}

int extractMin() {
    if (size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int root = heap[0];
    heap[0] = heap[--size];
    heapify(0);

    return root;
}

void buildMinHeap() {
    for (int i = size / 2 - 1; i >= 0; i--)
        heapify(i);
}

int main() {
    insert(5);
    insert(3);
    insert(4);
    insert(1);
    insert(2);
    insert(6);

    buildMinHeap();

    printf("Min Heap: ");
    for (int i = 0; i < size; i++)
        printf("%d ", heap[i]);
    printf("\n");

    printf("Extract Min: %d\n", extractMin());
    printf("Min Heap after extracting min: ");
    for (int i = 0; i < size; i++)
        printf("%d ", heap[i]);
    printf("\n");

    return 0;
}

Quiz 💡

That's all for today! We've learned about Min Heap, its properties, operations, and built a simple implementation in C. In the next lessons, we'll dive deeper into heap operations, explore heap sort, and more.

Happy coding! 💻🎓