C Programming Data Structures Heapify And Priority Queue Complete Guide

1. Heapify:

Heapify is the process of converting a binary tree into a heap data structure. This can be useful for implementing heapsort or other heap-related operations.

Types of Heaps:

• Max Heap: For each node i, the value of the node is greater than or equal to the values of its children.
• Min Heap: For each node i, the value of the node is less than or equal to the values of its children.

We'll implement max heapify.

Example: Max Heapify

Let's create a function to perform max heapify on a subtree rooted at index i. Assume the binary tree is almost a max heap except possibly for the node indexed i.

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify the subtree rooted at index i which is an index in arr[].
// n is size of heap
void maxHeapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left = 2*i + 1
    int right = 2 * i + 2; // right = 2*i + 2

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

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

    // If largest is not root
    if (largest != i) {
        swap(&arr[i], &arr[largest]);

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

int main() {
    // Define an array and size
    int arr[] = {3, 9, 2, 1, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int i = 1; // Index from where we want to apply max heapify
    printf("Original array: ");
    for(int j=0; j<n; j++) 
        printf("%d ", arr[j]);
        
    maxHeapify(arr, n, i);

    printf("\nArray after heapification: ");
    for(int j=0; j<n; j++) 
        printf("%d ", arr[j]);
    
    return 0;
}

Explanation:

• maxHeapify function ensures that subtree rooted at index i becomes a max heap.
• Parameters:
  • arr[]: Array representing the binary tree.
  • n: Number of elements in heap.
  • i: Node index to be "heapified".
• Steps:
  • Find the largest among root, left child, and right child.
  • Recursively heapify the affected subtree.

2. Priority Queue Using Heap

A priority queue is a special kind of queue in which each element is associated with a priority and dequeued based on the priority (higher priority elements are served before lower priority elements). Using heapify helps us in building this priority queue efficiently.

We'll demonstrate a priority queue using max heap.

Example: Max Priority Queue

Let's implement a priority queue that supports insertion and extraction of the maximum element.

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

// Function to swap two elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// A utility function to max heapify a subtree rooted with node i which is an index in arr[]
void maxHeapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2*i + 1; // left = 2*i + 1
    int right = 2*i + 2; // right = 2*i + 2

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

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

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}

// Function to insert a new node into the MaxHeap
void insertNode(int arr[], int* n, int key) {
    (*n)++;
    int i = *n - 1;
    arr[i] = key;

    while (i != 0 && arr[(i-1)/2] < arr[i]) {   // Fix the max heap property if it is violated
        swap(&arr[i], &arr[(i-1)/2]);
        i = (i-1)/2;
    }
}

// Function to delete the last node from MaxHeap
void deleteNode(int arr[], int* n) {
    int lastElement = arr[*n - 1];
    arr[0] = lastElement;
    (*n)--; 
    maxHeapify(arr, *n, 0);
}

// Function to get the maximum from the heap and delete it
int extractMax(int arr[], int* n) {
    // Store the maximum element
    int root = arr[0];

    // Replace root with last element
    int lastElement = arr[*n - 1];
    arr[0] = lastElement;
    (*n)--;

    // Call max heapify on the reduced heap
    maxHeapify(arr, *n, 0);

    return root;
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[10]; //= {12, 11, 13, 5, 6, 7};
    int capacity = 10;
    int n = 0;

    insertNode(arr, &n, 3);
    insertNode(arr, &n, 9);
    insertNode(arr, &n, 2);
    insertNode(arr, &n, 1);
    insertNode(arr, &n, 4);
    insertNode(arr, &n, 5);

    printArray(arr, n);
    printf("\nExtracted max element: %d\n", extractMax(arr, &n));
    
    printArray(arr, n);
    deleteNode(arr, &n);
    
    printArray(arr, n);

    return 0;
}

Explanation:

• Insertion: Add the new element at the end. Then move it up while it is smaller than its parent to maintain max heap property.
• Deletion: Move the last element to the root position and heapify the root node.
• Extraction of Maximum: This is similar to deletion, but we need to record the root node before replacing it with the last element. The root node was the largest element in the heap.

Summary