| 3 | # To heapify subtree rooted at index i. |
| 4 | # n is size of heap |
| 5 | def heapify(arr, n, i): |
| 6 | largest = i # Initialize largest as root |
| 7 | l = 2 * i + 1 # left = 2*i + 1 |
| 8 | r = 2 * i + 2 # right = 2*i + 2 |
| 9 | |
| 10 | # See if left child of root exists and is |
| 11 | # greater than root |
| 12 | if l < n and arr[i] < arr[l]: |
| 13 | largest = l |
| 14 | |
| 15 | # See if right child of root exists and is |
| 16 | # greater than root |
| 17 | if r < n and arr[largest] < arr[r]: |
| 18 | largest = r |
| 19 | |
| 20 | # Change root, if needed |
| 21 | if largest != i: |
| 22 | arr[i], arr[largest] = arr[largest], arr[i] # swap |
| 23 | |
| 24 | # Heapify the root. |
| 25 | heapify(arr, n, largest) |
| 26 | |
| 27 | |
| 28 | # The main function to sort an array of given size |