Heap Sort Algorithm
Heap Sort Algorithm is a comparison-based sorting technique that utilizes a binary heap data structure to efficiently sort a collection of data elements. This algorithm was introduced by J.W.J. Williams in 1964 as an in-place sorting algorithm with an excellent worst-case time complexity of O(n log n). Heap Sort is particularly suitable for sorting large data sets, as it takes advantage of the heap data structure's properties, which allows for efficient access and manipulation of the data.
The algorithm works by first constructing a binary heap (usually a max-heap) from the input data, where each parent node in the heap is greater than or equal to its child nodes. Once the heap is formed, the largest element (the root of the heap) is extracted and swapped with the last element of the heap. The heap size is then reduced by one, and the process is repeated by maintaining the max-heap property through a process called "heapifying" or "sifting down". This process is repeated until the entire heap is sorted, resulting in an ordered list of elements. The primary advantage of Heap Sort is its efficiency in sorting large data sets, as it has a consistent time complexity of O(n log n) regardless of the input distribution. However, it's worth noting that Heap Sort tends to be slower in practice when compared to other sorting algorithms like Quick Sort and Merge Sort due to its relatively high constant factors and poor cache performance.
#include <stdio.h>
void max_heapify(int* a, int i, int n);
void heapsort(int* a, int n);
void build_maxheap(int* a, int n);
void max_heapify(int* a, int i, int n) {
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n) {
if (j < n && a[j + 1] > a[j])
j = j + 1;
if (temp > a[j]) {
break;
} else if (temp <= a[j]) {
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j / 2] = temp;
return;
}
void heapsort(int* a, int n) {
int i, temp;
for (i = n; i >= 2; i--) {
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int* a, int n) {
int i;
for (i = n / 2; i >= 1; i--) {
max_heapify(a, i, n);
}
}
int main() {
int n, i;
printf("Enter number of elements of array\n");
scanf("%d", &n);
int a[20];
for (i = 1; i <= n; i++) {
printf("Enter Element %d\n", i);
scanf("%d", a + i);
}
build_maxheap(a, n);
heapsort(a, n);
printf("Sorted Output\n");
for (i = 1; i <= n; i++) {
printf("%d\n", a[i]);
}
getchar();
}
