Heap Sort Algorithm in C

Steps of Heap Sort Algorithm

Write a program to sort n randomly generated elements using heapsort method. ( assignment 2, set B. SPPU)

Build a Max Heap from the given elements.
Repeat the following steps until the heap size becomes 1:
- Swap the root (maximum element) with the last node in the array.
- Reduce the heap size by one.
- Apply the heapify procedure to restore the heap property.

Dear students , before you implement this program it recommande to uderstant the heapsort concept and heapsort algorithm. Use following links to read and understant the concept.

Heapsort as an application of Binary Tree.

Program in C

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

// Function to swap elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Heapify function to maintain max heap property
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child

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

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

// If largest is not the root
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // Recursively heapify the affected subtree
}
}

// Function to perform Heap Sort
void heapSort(int arr[], int n) {
// Step 1: Build Max Heap
for (int i = n / 2 – 1; i >= 0; i–)
heapify(arr, n, i);

// Step 2: Extract elements one by one
for (int i = n – 1; i > 0; i–) {
swap(&arr[0], &arr[i]); // Move current root to end
heapify(arr, i, 0); // Heapify the reduced heap
}
}

// Function to print array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf(“%d “, arr[i]);
printf(“\n”);
}

// Main function
int main() {
int n;
printf(“Enter the number of elements: “);
scanf(“%d”, &n);

int arr[n];

// Random number generation
srand(time(0));
printf(“Randomly generated array: “);
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100; // Generates numbers between 0-99
printf(“%d “, arr[i]);
}

printf(“\n”);

// Sorting the array using Heap Sort
heapSort(arr, n);

printf(“Sorted array: “);
printArray(arr, n);

return 0;
}