-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap_sort.py
38 lines (30 loc) · 1.11 KB
/
heap_sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# O(nlog(n)) time | O(1) space
def heapSort(array):
buildMaxHeap(array)
for endIdx in reversed(range(1, len(array))):
swap(0, endIdx, array)
siftDown(0, endIdx - 1, array)
return array
def buildMaxHeap(array):
firstParentIdx = (len(array) - 1) // 2
for currentIdx in reversed(range(firstParentIdx + 1)):
siftDown(currentIdx, len(array) - 1, array)
def siftDown(currentIdx, endIdx, heap):
childOneIdx = currentIdx * 2 + 1
while childOneIdx <= endIdx:
childTwoIdx = currentIdx * 2 + 2 if currentIdx * 2 + 2 <= endIdx else -1
if childTwoIdx > -1 and heap[childTwoIdx] > heap[childOneIdx]:
idxToSwap = childTwoIdx
else:
idxToSwap = childOneIdx
if heap[idxToSwap] > heap[currentIdx]:
swap(currentIdx, idxToSwap, heap)
currentIdx = idxToSwap
childOneIdx = currentIdx * 2 + 1
else:
return
def swap(i, j, array):
array[i], array[j] = array[j], array[i]
if __name__ == '__main__':
array = [8, 5, 2, 9, 5, 6, 3]
print(heapSort(array))