堆排序
思路
堆排序思路是：
- 将数组以二叉树的形式分析，令根节点索引值为0，索引值为index的节点，子节点索引值分别为index*2+1、index*2+2；
- 对二叉树进行维护，使得每个非叶子节点的值，都大于或者小于其子节点的值，两种分别称为大根堆、小根堆，其中二叉树根节点的值就是数组的最大值或最小值；
- 将二叉树根节点取出，维护后的数组最后一个元素移至根节点，再重新进行上述维护；
- 循环上述步骤，直到数组所有元素均被取出，则取出的所有元素组成的序列有序，从而实现排序的目的。
代码实例
实现代码如下：
h=list(map(int,input().split()))
def heapSort(root):
# 本质上，heapSort实现的是，根据小根堆的规则，将二叉树根节点root的值h[root]向下移动，
# 直到h[root]到达某处，该处root的两个子节点值均大于h[root]。
# 如果root下面两边的子二叉树均符合小根堆，那么处理之后，以root为根节点的二叉树同样符合小根堆。
a=root
# 节点root的左子结点是root*2+1，右子节点是root*2+2
if root*2+1<len(h) and h[a]>h[root*2+1]:
a=root*2+1
# 如果是，则此时a就是左子节点索引，否，则a仍是根节点索引
if root*2+2<len(h) and h[a]>h[root*2+2]:
a=root*2+2
# 此时a就是root节点以及其两个子节点里面最小值的索引
if a!=root: # a此时是子节点索引值
h[a],h[root]=h[root],h[a] # 保证根节点值最小
heapSort(a) # 从上往下递归处理
else: # 要么，根节点已经是最小的了，要么，根节点没有子节点，不用排序
return
for i in range(len(h)//2,-1,-1):
heapSort(i)
# 从二叉树的底部开始处理，保证每次处理某个节点时，下面的子二叉树已经符合小根堆。
# print(h)
length=len(h)
for _ in range(length):
if len(h)!=1:
h[0],h[-1]=h[-1],h[0]
print(h.pop(),end=" ")
heapSort(0)
else:
print(h.pop(),end=" ")heapSort函数维护的是小根堆，此时代码输出内容就是列表h中元素从小到大排序的序列。
堆排序实质上很容易获取当前列表中最值，因此，topK问题（输出列表中前K个最大/小值）很适合用堆排序处理。
python内置模块——heapq
常用函数
-
heappush(heap,item)：向列表heap中添加元素item，添加时会保证heap仍然是小根堆，时间复杂度为O(log(len(heap)))
-
heapify(heap)：以线性时间将列表heap转化为小根堆
-
heappop(heap)：从堆heap中弹出并返回最小的值
注意点
1. 如果要建立大根堆，可以考虑所有元素取负值，此时堆本身为小根堆，但我们自己希望的元素存储形式上是大根堆。 2. 调用heappush时，添加的item可以是一个数，此时就是根据item值维护小根堆；但是item也可以是元组，此时维护标准是元组中第0个元素，当不同元组间，前一个元素相同，则参考下一个元素。
代码实例
AcWing:Dijkstra求最短路 II
实例题目中，有向边的数量与节点数量相近，可见，此时该图为稀疏图。Dijkstra算法求最短路中，在获取当前与1号点最短距离的节点时，一般是选择遍历所有节点获取，但是本题的图为稀疏图，且节点数量众多，此时会导致代码获取节点时间复杂度为O()，显然时间复杂度过高。
此时换另一个思路：不选择遍历所有节点，而是存储已处理的节点，并且每次直接获取到最短距离的节点。该方式可以联想到小根堆，小根堆堆顶元素刚好可以符合要求。此时即可调用heapq库，使用其中的函数维护小根堆，便能实现本题目标。
代码：
import heapq #本题需要使用到堆排序
n,m=map(int,input().split())
edge=[[] for _ in range(n+1)] # edge[i][j]=[节点i的第j个邻接有向边指向的节点编号,该边长度]
distance=[1000000000 for _ in range(n+1)] # distance[i]=当前最短通路长度
visited=[False for _ in range(n+1)]
for _ in range(m):
a,b,d=map(int,input().split())
edge[a].append([b,d])
distance[1]=0
heapDis=[(0,1)]
while len(heapDis):
#print(edge[now])
dis,now=heapq.heappop(heapDis)
if visited[now]:
continue
visited[now] = True
for next, edgeDis in edge[now]:
if distance[now]+edgeDis<distance[next]:
distance[next]=distance[now]+edgeDis
heapq.heappush(heapDis, (distance[next], next))
# 总计有m条边，最多会向heapDis中添加m次元素
# 每次添加元素，最大时间复杂度为O(logn)
# 因此，总的时间复杂度为O(mlogn)
if distance[n]>10e9:
print(-1)
else:
print(distance[n])
