1#include <iostream>
2
3using namespace std;
4
5
6void heapify(int arr[], int n, int i)
7{
8 int largest = i;
9 int l = 2 * i + 1;
10 int r = 2 * i + 2;
11
12
13 if (l < n && arr[l] > arr[largest])
14 largest = l;
15
16
17 if (r < n && arr[r] > arr[largest])
18 largest = r;
19
20
21 if (largest != i) {
22 swap(arr[i], arr[largest]);
23
24
25 heapify(arr, n, largest);
26 }
27}
28
29
30void heapSort(int arr[], int n)
31{
32
33 for (int i = n / 2 - 1; i >= 0; i--)
34 heapify(arr, n, i);
35
36
37 for (int i = n - 1; i > 0; i--) {
38
39 swap(arr[0], arr[i]);
40 heapify(arr, i, 0);
41 }
42}
43
44
45void printArray(int arr[], int n)
46{
47 for (int i = 0; i < n; ++i)
48 cout << arr[i] << " ";
49 cout << "\n";
50}
51
52
53int main()
54{
55 int arr[] = { 12, 11, 13, 5, 6, 7 };
56 int n = sizeof(arr) / sizeof(arr[0]);
57
58 heapSort(arr, n);
59
60 cout << "Sorted array is \n";
61 printArray(arr, n);
62}
1Implementation of heap sort in C:
2
3#include <stdio.h>
4int main()
5{
6 int heap[10], array_size, i, j, c, root, temporary;
7 printf("\n Enter size of array to be sorted :");
8 scanf("%d", &array_size);
9 printf("\n Enter the elements of array : ");
10 for (i = 0; i < array_size; i++)
11 scanf("%d", &heap[i]);
12 for (i = 1; i < array_size; i++)
13 {
14 c = i;
15 do
16 {
17 root = (c - 1) / 2;
18 if (heap[root] < heap[c]) /* to create MAX heap array */
19 { // if child is greater than parent swap them
20 temporary = heap[root]; // as structure is of complete binary tree
21 heap[root] = heap[c]; // it took logn steps to reach from root to leaf
22 heap[c] = temporary;
23 }
24 c = root;
25 } while (c != 0);
26 }
27 printf("Heap array : ");
28 for (i = 0; i < array_size; i++)
29 printf("%d\t ", heap[i]); //printing the heap array
30 for (j = array_size - 1; j >= 0; j--)
31 {
32 temporary = heap[0];
33 heap[0] = heap[j] ; /* swap max element with rightmost leaf element */
34 heap[j] = temporary;
35 root = 0;
36 do
37 {
38 c = 2 * root + 1; /* left node of root element */
39 if ((heap[c] < heap[c + 1]) && c < j-1)
40 c++;
41 if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
42 {
43 temporary = heap[root];
44 heap[root] = heap[c];
45 heap[c] = temporary;
46 }
47 root = c;
48 } while (c < j);
49 }
50 printf("\n The sorted array is : ");
51 for (i = 0; i < array_size; i++)
52 printf("\t %d", heap[i]);
53}