Simple2Code

Implementation of HeapSort Algorithm in C

Written by

admin

in

In this tutorial, we will write a C program to implement heap sort. Before that, you may go through the following topics in C.

Heap Sort Algorithm

Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.

Heapsort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on a Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees

Binary heap

Learn more on Heap sort.

Implementation of HeapSort Algorithm in C

Question: C program to implement Heap sort using function.

// implementation of heap sort in C program

#include <stdio.h>

//function prototype
void heapSort(int arr[], int n);
void heapify(int arr[], int size, int i);

//main function
int main()
{
  int arr[30], n, i;

  printf("Enter the number of elements: ");
  scanf("%d", &n);

  printf("Enter %d Elements:\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

  //calling sorting function
  heapSort(arr, n);

  //Display the result
  printf("\nArray after sorting: \n");
  for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

  return 0;
}

void heapSort(int arr[], int n)
{
  // create heap
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  // One by one extract an element from heap
  for (int i = n - 1; i > 0; i--)
  {
    // arrA[0] being max element
    int x = arr[0];
    arr[0] = arr[i];
    arr[i] = x;

    // call max 
    heapify(arr, i, 0);
  }
}

void heapify(int arr[], int size, int i)
{
  int largest = i;  // root

  //Indexes
  int leftChild = 2 *i + 1;
  int rightChild = 2 *i + 2;

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

  // If right child is larger than root
  if (rightChild < size && arr[rightChild] > arr[largest])
    largest = rightChild;

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

    // Recursive call
    heapify(arr, size, largest);
  }
}

Output:

Enter the number of elements: 6
Enter 6 Elements:
25
98
3
124
66
9

Array after sorting:
3 9 25 66 98 124

More posts