1// Aim: Program to perform Heap Sort on an array.
2#include <stdio.h>
3
4void swap(int* a, int* b){
5	int temp = *a;
6	*a = *b;
7	*b = temp;
8}
9
10void heapify(int arr[], int N, int i){
11	int largest = i;
12	int left = 2 * i + 1;
13	int right = 2 * i + 2;
14	if (left < N && arr[left] > arr[largest])
15		largest = left;
16	if (right < N && arr[right] > arr[largest])
17		largest = right;
18	if (largest != i) {
19		swap(&arr[i], &arr[largest]);
20		heapify(arr, N, largest);
21	}
22}
23
24
25void heapSort(int arr[], int N){
26	for (int i = N / 2 - 1; i >= 0; i--)
27		heapify(arr, N, i);
28	for (int i = N - 1; i >= 0; i--) {
29		swap(&arr[0], &arr[i]);
30		heapify(arr, i, 0);
31	}
32}
33
34
35void printArray(int arr[], int N)
36{
37	for (int i = 0; i < N; i++)
38		printf("%d ", arr[i]);
39	printf("\n");
40}
41int main() {
42	int N;
43	printf("Enter number of elements: ");
44	scanf("%d", &N);
45	int arr[N];
46	printf("Enter %d elements: ", N);
47	for (int i = 0; i < N; i++) {
48		scanf("%d", &arr[i]);
49	}
50	heapSort(arr, N);
51	printf("Sorted array is: ");
52	printArray(arr, N);
53	return 0;
54}