Skip to content

Instantly share code, notes, and snippets.

@tuvo1106
Created July 4, 2019 16:55
Show Gist options
  • Save tuvo1106/267a2b58f06bebdbc1f9a4cda809e1f2 to your computer and use it in GitHub Desktop.
Save tuvo1106/267a2b58f06bebdbc1f9a4cda809e1f2 to your computer and use it in GitHub Desktop.
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(l: list):
arr = l[::]
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment