| 5 | |
| 6 | |
| 7 | def refineHeap(arr, n, i): |
| 8 | # Initialize the largest entry as the root of the heap |
| 9 | largest = i |
| 10 | left = 2 * i + 1 |
| 11 | right = 2 * i + 2 |
| 12 | |
| 13 | # If the left child exists and it is larger than largest, replace it |
| 14 | if left < n and arr[largest] < arr[left]: |
| 15 | largest = left |
| 16 | |
| 17 | # Perform the same operation for the right hand side of the heap |
| 18 | if right < n and arr[largest] < arr[right]: |
| 19 | largest = right |
| 20 | |
| 21 | # Change root if the largest value changed |
| 22 | if largest != i: |
| 23 | arr[i], arr[largest] = arr[largest], arr[i] |
| 24 | |
| 25 | # Repeat the process until the heap is fully defined |
| 26 | refineHeap(arr, n, largest) |
| 27 | |
| 28 | |
| 29 | # Main function |