C Programming: Heap Data Structure 🎯

Welcome to our deep dive into the Heap Data Structure in C programming! This lesson is designed for beginners and intermediates, so don't worry if you're new to the concept. Let's get started!

Understanding the Heap 📝

A Heap is a specialized tree-based data structure that satisfies the heap property. It's often used for implementing priority queues. In a Max Heap, the parent node is always greater than or equal to its children, while in a Min Heap, the parent node is always less than or equal to its children.

Creating a Heap ✅

To create a heap in C, we typically use an array to represent the heap. The root of the heap is at index 1, not 0, because we reserve index 0 for sentinel value (often -1 or INT_MAX).

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

#define SIZE 10

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i;
    int r = 2 * i + 1;

    // If left child is larger than root
    if (l <= n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r <= n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

Building a Heap 💡

To build a Max Heap, we first create the heap array and insert all elements. After inserting all elements, we call the heapify function for the last element, which is the root of the heap, and then work our way down to maintain the heap property.

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

Heap Operations ✅

Insert: To insert an element, we append it to the end of the array, then call the buildHeap function to maintain the heap property.
Extract Max: To extract the maximum element, we swap the last and root elements, then heapify the new root.
Decrease Key: To decrease the key of an element, we first find the element, then change its value and call heapify to maintain the heap property.

C Programming: Heap Data Structure 🎯

C Programming: Heap Data Structure 🎯

Understanding the Heap 📝

Creating a Heap ✅

Building a Heap 💡

Heap Operations ✅

Quiz 💡