Created
May 28, 2025 08:33
-
-
Save Seniru/956879ab6755ac7c39798d347e94f7b0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """heapify algorithm | |
| Creates a max heap from an unsorted array. The logic behind this is the parent node should be larger than | |
| its children. Therefore, if one of those children have greater values, swap the parent with its child. | |
| By doing this repeatedly, we can guarantee each nodes' value is higher than its children' | |
| """ | |
| def heapify(arr, n, i): | |
| largest = i | |
| left = 2 * i + 1 | |
| right = 2 * i + 2 | |
| if left < n and arr[left] > arr[largest]: | |
| largest = left | |
| if right < n and arr[right] > arr[largest]: | |
| largest = right | |
| if largest != i: | |
| arr[largest], arr[i] = arr[i], arr[largest] | |
| heapify(arr, n, largest) | |
| """build_max_heap algorithm | |
| """ | |
| def build_max_heap(arr, n): | |
| for i in range(n // 2, -1, -1): | |
| heapify(arr, n, i) | |
| """heapsort algorithm | |
| """ | |
| def heapsort(arr): | |
| n = len(arr) | |
| # To perform a heapsort, first the array has to be turned in to a max heap (we are using build_max_heap here). | |
| # A max heap ensures that the value at the 0th index is the highest. | |
| build_max_heap(arr, n) | |
| for i in range(n - 1, -1, -1): | |
| # because of the max heap property, value at the 0th index owuld always be the highest (local), | |
| # therefore swap it with the last element | |
| arr[i], arr[0] = arr[0], arr[i] | |
| # then heapify again to bring the next highest value to the root of the heap | |
| heapify(arr, i, 0) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment