function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */
| 3 | /* function to heapify a subtree. Here 'i' is the |
| 4 | index of root node in array a[], and 'n' is the size of heap. */ |
| 5 | void heapify(int a[], int n, int i) |
| 6 | { |
| 7 | int largest = i; // Initialize largest as root |
| 8 | int left = 2 * i + 1; // left child |
| 9 | int right = 2 * i + 2; // right child |
| 10 | // If left child is larger than root |
| 11 | if (left < n && a[left] > a[largest]) |
| 12 | largest = left; |
| 13 | // If right child is larger than root |
| 14 | if (right < n && a[right] > a[largest]) |
| 15 | largest = right; |
| 16 | // If root is not largest |
| 17 | if (largest != i) { |
| 18 | // swap a[i] with a[largest] |
| 19 | int temp = a[i]; |
| 20 | a[i] = a[largest]; |
| 21 | a[largest] = temp; |
| 22 | |
| 23 | heapify(a, n, largest); |
| 24 | } |
| 25 | } |
| 26 | /*Function to implement the heap sort*/ |
| 27 | void heapSort(int a[], int n) |
| 28 | { |