C Max Heap 🎯

Welcome to our deep dive into C Max Heap! This lesson is designed for beginners and intermediate learners who want to understand and implement Max Heap in C programming. By the end of this tutorial, you'll not only know what a Max Heap is but also learn how to create one and apply it to real-world problems. 📝 Let's get started!

Introduction 📝

A Max Heap is a special type of Heap data structure in computer science that always stores the maximum value at the root node. The beauty of Max Heap is that it follows a specific property known as the "heap property," which we'll explore in this lesson.

Heap Property 📝

For a Max Heap, the heap property states that the key value of a parent node is greater than or equal to the key values of its child nodes. This property ensures the max value is always at the root of the heap. 💡 Pro Tip: In C, we use a binary heap, which means each node can have at most two children.

Building a Max Heap 📝

Let's build a Max Heap from scratch using an array.

#include <stdio.h>

void maxHeapify(int arr[], int n, int i) {
    int left = 2 * i;
    int right = 2 * i + 1;
    int largest = i;

    if (left <= n && arr[left] > arr[largest])
        largest = left;

    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        maxHeapify(arr, n, largest);
    }
}

void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2; i >= 1; i--) {
        maxHeapify(arr, n, i);
    }
}

Let's take a look at the maxHeapify() function first. This function ensures the heap property is maintained by swapping the largest value with its child, if necessary, and recursively applying the same process to the affected subtree.

The buildMaxHeap() function initializes the Max Heap by calling maxHeapify() on each parent node in the array.

Practical Application 🎯

Now that we have a Max Heap, let's see it in action! A common application of Max Heap is in priority queue implementations, where the highest priority items are always at the front.

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

typedef struct Node {
    int data;
    int priority;
} Node;

int compare(const void* a, const void* b) {
    Node* nodeA = (Node*)a;
    Node* nodeB = (Node*)b;

    return nodeA->priority - nodeB->priority;
}

void enqueue(Node* queue[], int capacity, Node* data) {
    if (queue[capacity] == NULL) {
        queue[capacity] = data;
    } else {
        int i = capacity;
        while (i > 1 && data->priority > queue[i/2]->priority) {
            queue[i] = queue[i/2];
            i /= 2;
        }
        queue[i] = data;
    }
}

void dequeue(Node* queue[], int* capacity) {
    if (*capacity == 0)
        return;

    Node* root = queue[1];
    queue[1] = queue[*capacity];
    (*capacity)--;
    maxHeapify(queue, *capacity, 1);

    printf("Dequeued: %d\n", root->data);
}

void maxHeapify(Node* arr[], int n, int i) {
    int left = 2 * i;
    int right = 2 * i + 1;
    int largest = i;

    if (left <= n && arr[left]->priority > arr[largest]->priority)
        largest = left;

    if (right <= n && arr[right]->priority > arr[largest]->priority)
        largest = right;

    if (largest != i) {
        Node* temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        maxHeapify(arr, n, largest);
    }
}

int main() {
    Node* queue[10] = {NULL};

    enqueue(queue, 10, malloc(sizeof(Node)) * (sizeof(Node)/sizeof(int)));
    ((Node*)queue[1])->data = 1;
    ((Node*)queue[1])->priority = 1;

    enqueue(queue, 10, malloc(sizeof(Node)) * (sizeof(Node)/sizeof(int)));
    ((Node*)queue[2])->data = 2;
    ((Node*)queue[2])->priority = 2;

    enqueue(queue, 10, malloc(sizeof(Node)) * (sizeof(Node)/sizeof(int)));
    ((Node*)queue[3])->data = 3;
    ((Node*)queue[3])->priority = 3;

    enqueue(queue, 10, malloc(sizeof(Node)) * (sizeof(Node)/sizeof(int)));
    ((Node*)queue[4])->data = 4;
    ((Node*)queue[4])->priority = 1;

    buildMaxHeap(queue, 10);

    dequeue(queue, &capacity);
    dequeue(queue, &capacity);
    dequeue(queue, &capacity);
    dequeue(queue, &capacity);

    return 0;
}

In this example, we have a priority queue implemented as a Max Heap. We enqueue tasks with their priorities and dequeue the highest priority task first.

Quiz Time 🎯

That's all for today's lesson on C Max Heap! We hope you found it helpful and engaging. Stay tuned for more in-depth programming tutorials at CodeYourCraft. Happy coding! 💡 Pro Tip: Practice building Max Heaps and implementing them in practical applications to solidify your understanding.