Bootcamp
Searchโฆ
A.5.8.1: Heap Sort
In D.7 we mentioned heap sort that runs in `O(nlogn) time.` Now that we've covered heaps we can look at this algo again.

## Heap Sort

• Runtime: O(nlogn)
• Space: O(1)
• Sort In-Place: Yes
• Stable: Yes

### Attributes

• good space complexity
• not favored compared to quicksort
def heapify(arr, n, i):
# Find largest among root and children
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 root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
โ
โ
def heapSort(arr):
n = len(arr)
โ
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
โ
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
โ
# Heapify root element
heapify(arr, i, 0)
โ
โ
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')