Python学习笔记——heapq_heapq 时间复杂的

堆排序

思路

堆排序思路是：

1. 将数组以二叉树的形式分析，令根节点索引值为0，索引值为index的节点，子节点索引值分别为index*2+1、index*2+2；
2. 对二叉树进行维护，使得每个非叶子节点的值，都大于或者小于其子节点的值，两种分别称为大根堆、小根堆，其中二叉树根节点的值就是数组的最大值或最小值；
3. 将二叉树根节点取出，维护后的数组最后一个元素移至根节点，再重新进行上述维护；
4. 循环上述步骤，直到数组所有元素均被取出，则取出的所有元素组成的序列有序，从而实现排序的目的。

代码实例

实现代码如下：

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])