Python 算法教程（7）：堆排序详解
前言
堆排序利用堆这种数据结构，时间复杂度 O(n log n)。
一、算法原理
1.建堆 2.交换堆顶与末尾 3.调整堆 4.重复
二、代码实现
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)三、复杂度
时间 O(n log n)，空间 O(1)，不稳定
四、应用
TopK 问题、优先队列
总结
堆排序性能稳定，适合 TopK 问题。
下一篇：二分查找
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
