| 65 | // To heapify a subtree rooted with node i which is |
| 66 | // an index in arr[]. n is size of heap |
| 67 | void heapify(int arr[], int n, int i) |
| 68 | { |
| 69 | int largest = i; // Initialize largest as root |
| 70 | int l = 2*i + 1; // left = 2*i + 1 |
| 71 | int r = 2*i + 2; // right = 2*i + 2 |
| 72 | |
| 73 | // If left child is larger than root |
| 74 | if (l < n && arr[l] > arr[largest]) |
| 75 | largest = l; |
| 76 | |
| 77 | // If right child is larger than largest so far |
| 78 | if (r < n && arr[r] > arr[largest]) |
| 79 | largest = r; |
| 80 | |
| 81 | // If largest is not root |
| 82 | if (largest != i) |
| 83 | { |
| 84 | int swap = arr[i]; |
| 85 | arr[i] = arr[largest]; |
| 86 | arr[largest] = swap; |
| 87 | |
| 88 | // Recursively heapify the affected sub-tree |
| 89 | heapify(arr, n, largest); |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | /* A utility function to print array of size n */ |
| 94 | static void printArray(int arr[]) |