- 时间复杂度O(nlogN)
- 不稳定排序
def heapify(tree, n, i):
if i >= n:
return
max_index = i
left_child = 2*i + 1
right_child = left_child + 1
if left_child < n and tree[max_index] < tree[left_child]:
max_index = left_child
if right_child < n and tree[max_index] < tree[right_child]:
max_index = right_child
if max_index != i:
tree[i], tree[max_index] = tree[max_index], tree[i]
heapify(tree, n, max_index)
def build_heap(arr):
last_node = len(arr) - 1
parent = (last_node - 1) // 2
for i in range(parent, -1, -1):
heapify(arr, last_node, i)
def heap_sort(arr):
build_heap(arr)
for i in range(1, len(arr)):
arr[0], arr[len(arr)-i] = arr[len(arr)-i], arr[0]
heapify(arr, len(arr)-i-1, 0)