堆排序——heapq

简介

堆是一种树形结构,父子节点之间是有序的,大顶堆即,父节点大于等于两个子节点,小顶堆相反。Python的headpq模块实现了列表的小顶堆排序算法。

建堆

两种方式,heappush()heapify()

1
2
3
4
5
6
import heapq
a=[1,5,9,2,10,4]
heap=[]
for n in a:
heapq.heappush(heap,n)
print(heap) #[1, 2, 4, 5, 10, 9]

删除最小值

heappop()

1
2
3
4
5
import heapq
a=[1,5,9,2,10,4]
#建堆
heapq.heapify(a)
print(heapq.heappop(a)) # print 1

替换最小值

heapreplace()

1
2
3
4
5
import heapq
a=[1,5,9,2,10,4]
#建堆
heapq.heapify(a)
heapq.heapreplace(a,6) # print 1 、a=[2, 5, 4, 6, 10, 9]

堆排序

1
2
3
4
from heapq import *
def heapsort(data):
[heappush(heap,n) for n in data]
return [heappop(heap) for i in range(len(heap))]
分享