安乡网站制作,网站前端 设计,wordpress离线文章发布,wordpress文章浏览数堆排序
思路
堆排序思路是#xff1a;
将数组以二叉树的形式分析#xff0c;令根节点索引值为0#xff0c;索引值为index的节点#xff0c;子节点索引值分别为index*21、index*22#xff1b;对二叉树进行维护#xff0c;使得每个非叶子节点的值#xff0c;都大于或者…堆排序
思路
堆排序思路是
将数组以二叉树的形式分析令根节点索引值为0索引值为index的节点子节点索引值分别为index*21、index*22对二叉树进行维护使得每个非叶子节点的值都大于或者小于其子节点的值两种分别称为大根堆、小根堆其中二叉树根节点的值就是数组的最大值或最小值将二叉树根节点取出维护后的数组最后一个元素移至根节点再重新进行上述维护循环上述步骤直到数组所有元素均被取出则取出的所有元素组成的序列有序从而实现排序的目的。
代码实例
实现代码如下
hlist(map(int,input().split()))def heapSort(root):# 本质上heapSort实现的是根据小根堆的规则将二叉树根节点root的值h[root]向下移动# 直到h[root]到达某处该处root的两个子节点值均大于h[root]。# 如果root下面两边的子二叉树均符合小根堆那么处理之后以root为根节点的二叉树同样符合小根堆。aroot# 节点root的左子结点是root*21右子节点是root*22if root*21len(h) and h[a]h[root*21]:aroot*21# 如果是则此时a就是左子节点索引否则a仍是根节点索引if root*22len(h) and h[a]h[root*22]:aroot*22# 此时a就是root节点以及其两个子节点里面最小值的索引if a!root: # a此时是子节点索引值h[a],h[root]h[root],h[a] # 保证根节点值最小heapSort(a) # 从上往下递归处理else: # 要么根节点已经是最小的了要么根节点没有子节点不用排序returnfor i in range(len(h)//2,-1,-1):heapSort(i)# 从二叉树的底部开始处理保证每次处理某个节点时下面的子二叉树已经符合小根堆。
# print(h)lengthlen(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,mmap(int,input().split())
edge[[] for _ in range(n1)] # edge[i][j][节点i的第j个邻接有向边指向的节点编号,该边长度]
distance[1000000000 for _ in range(n1)] # distance[i]当前最短通路长度
visited[False for _ in range(n1)]
for _ in range(m):a,b,dmap(int,input().split())edge[a].append([b,d])
distance[1]0
heapDis[(0,1)]
while len(heapDis):#print(edge[now])dis,nowheapq.heappop(heapDis)if visited[now]:continuevisited[now] Truefor next, edgeDis in edge[now]:if distance[now]edgeDisdistance[next]:distance[next]distance[now]edgeDisheapq.heappush(heapDis, (distance[next], next))# 总计有m条边最多会向heapDis中添加m次元素# 每次添加元素最大时间复杂度为O(logn)# 因此总的时间复杂度为O(mlogn)if distance[n]10e9:print(-1)
else:print(distance[n])
