heap sort code in c code example
Example 1: heapify in c
#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(int array[], int size, int i)
{
if (size == 1)
{
printf("Single element in the heap");
}
else
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
if (largest != i)
{
swap(&array[i], &array[largest]);
heapify(array, size, largest);
}
}
}
void insert(int array[], int newNum)
{
if (size == 0)
{
array[0] = newNum;
size += 1;
}
else
{
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
}
void deleteRoot(int array[], int num)
{
int i;
for (i = 0; i < size; i++)
{
if (num == array[i])
break;
}
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Max-Heap array: ");
printArray(array, size);
deleteRoot(array, 4);
printf("After deleting an element: ");
printArray(array, size);
}
Example 2: heap sort heapify and max heap in binary tree
Implementation of heap sort in C:
#include <stdio.h>
int main()
{
int heap[10], array_size, i, j, c, root, temporary;
printf("\n Enter size of array to be sorted :");
scanf("%d", &array_size);
printf("\n Enter the elements of array : ");
for (i = 0; i < array_size; i++)
scanf("%d", &heap[i]);
for (i = 1; i < array_size; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c])
{
temporary = heap[root];
heap[root] = heap[c];
heap[c] = temporary;
}
c = root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < array_size; i++)
printf("%d\t ", heap[i]);
for (j = array_size - 1; j >= 0; j--)
{
temporary = heap[0];
heap[0] = heap[j] ;
heap[j] = temporary;
root = 0;
do
{
c = 2 * root + 1;
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j)
{
temporary = heap[root];
heap[root] = heap[c];
heap[c] = temporary;
}
root = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < array_size; i++)
printf("\t %d", heap[i]);
}