| 3 | #function of heapify |
| 4 | #n=size of heap |
| 5 | def heapify(arr, n, i): |
| 6 | largest = i #initialize the largest as the root |
| 7 | l = 2 * i + 1#check child of left = 2*i + 1 |
| 8 | r = 2 * i + 2#check child of right = 2*i + 2 |
| 9 | |
| 10 | #if left child of root exists and > than root |
| 11 | if l < n and arr[largest] < arr[l]: |
| 12 | largest = l |
| 13 | |
| 14 | #if right child of root exists and > than root |
| 15 | if r < n and arr[largest] < arr[r]: |
| 16 | largest = r |
| 17 | |
| 18 | #changing the root to largest |
| 19 | if largest != i: |
| 20 | arr[i], arr[largest] = arr[largest], arr[i] |
| 21 | #heapify the root. |
| 22 | heapify(arr, n, largest) |
| 23 | |
| 24 | #function heapsort to sort |
| 25 | def heapSort(arr): |