NB排序算法 - 堆排序
Created: March 9, 2022 8:11 PM
Introduction: 介绍堆排序
Source: 原创
Tags: 算法专栏
堆排序 - 什么是堆
堆：一种特殊的完全二叉树结构，其分为以下两种：
- 大根堆：一棵完全二叉树，满足任意一节点都比其孩子节点大
- 小根堆：一棵完全二叉树，满足任意一节点都比其孩子节点小
如图所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5RpI10fZ-174156832)(NB%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%20-%20%E5%A0%86%202d06c/Untitled.png)]
堆的向下调整
假设：节点的左右子树都是堆，但自身不是堆，即下图这种情况：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8Qm4QMay-174156838)(NB%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%20-%20%E5%A0%86%202d06c/Untitled%201.png)]
请问这个是堆吗？ 不是，原因就在于不满足大小堆的条件，其根节点比其孩子节点小，其余节点皆比其孩子节点大
此时就可以通过向下调整来将其变换成一个堆：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1pD7dxr0-17415683901)(NB%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%20-%20%E5%A0%86%202d06c/Untitled%202.png)]
堆排序的过程
向下调整方法：
def sift(li,low,high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low
j = 2 * i + 1
tmp = li[low]
while j <= high:
if j + 1 <= high and li[j+1] > li[j]:
j += 1
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
li[i] = tmp
break
else:
li[i] = tmp
堆排序方法：
def heap_sort(li):
n = len(li)
for i in range((n-1-1) // 2,-1,-1):
sift(li,i,n)
for i in range(n-1,-1,-1):
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)
堆排序的效率
- 向下调整过程时间复杂度：
O
(
l
o
g
n
)
O(logn)
O(logn)
- 整个堆排序时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
Python内置堆排序模块
python内置好了堆排序模块，要使用只需导入heapq模块即可
import heapq
如果利用其进行堆排序呢？
heapq.heapify(li)
for i in range(len(li)):
print(heapq.heappop(li),end=',')
堆排序 - topk问题
解决思路：
- 排序后切片：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
- 排序LowB三人组：
O
(
k
n
)
O(kn)
O(kn)
如果只需要求前k大的数，其实用LowB排序更好，排序k趟，不用像堆排序一样先全部排好序再取前k大的数。
更好的方法：堆排序思路
O
(
n
l
o
g
k
)
O(nlogk)
O(nlogk)
- 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
- 遍历列表所有元素后，倒序弹出堆顶。
def topk(li,k):
heap = li[0:k]
for i in range((k-2)//2,-1,-1):
sift(heap,i,k-1)
for i in range(k,len(li)):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
for i in range(k-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
return heap
相关参考
清华大学博士讲解Python数据结构与算法：
