基于Python的堆优化单源最短路径

本文主要是本人对堆优化单源最短路径中堆的一些理解，如有需要还会发布对单源最短路径的解释。参考书目：Algorithms Design Techniques and Analysis【沙特】M.H.Alsuwaiyel，如有错误欢迎留言指出，谢谢。

在了解最小堆的特性之后，首先，要实现堆运算Sift_up,假定对于某个i，其键值变成了小于父节点的键值元素，这样就违反了最小堆的特性，所以要通过Sift_up，把这个不符合最小堆特性的数据项重新转移到二叉树的合适位置，以此修复最小堆的特性。具体代码如下：

def SIFT_UP(H,i,k):#H为堆，k为堆中数据项的键值done = Falseif i==1:return print(f"节点{i}为根")while i>1 or not done:if i>1:#在堆中，忽略H[0],因此在此代码中H[0]=inf,为避免H[i//2-1]取到inf，在此加入限制条件a=int(H[i]-1)b=int(H[i // 2]-1)if k[a]<k[b]:H[i],H[i//2]=H[i//2],H[i]else: done =Truei = i//2else:break

其次，在实际运算中，我们也会遇到存储在H中的数据项的键值有小于其子节点的键值的，这样也不符合最小堆的特性，因此需要用堆运算Sift_down,把这个不合适的数据项重新转移到合适的位置。具体代码如下：

def SIFT_down(H,i,k):a =  int(H[i] - 1)b = int(H[i // 2] - 1)c = int(H[i+1]-1)n = len(H)-1done = Falseif 2*i>n:print(f"节点{i}是叶子")while 2*i<=n or not done:i=2*iif i+1<=n and k[c]<k[a]:i=i+1if i<=n:#H[i]在列表内的时候，执行以下语句if k[b]>k[a]:H[i],H[i//2]=H[i//2],H[i]else:done = True

在实际运算中，我们可能需要对堆中的一些数据项进行删除处理，为了使删除数据项之后的堆依旧符合最小堆的特性，就需要对堆进行Sift_up或Sift_down运算，直到满足堆的特性。具体的删除代码如下：

"""要从大小为n的堆H中删除第i个元素，可以先用第n个元素替代第i个元素，然后将堆的大小减1"""
def delete(H,i,k):x=H[i]n=len(H)-1y=H[n]del H[n]if i==n+1:print("完成")if i==len(H):print(k)else:H[i]=yif k[y-1]>=k[x-1]:SIFT_UP(H,i,k)else:SIFT_down(H,i,k)

在实际运算中也要运用到插入堆的运算，插入堆与堆的Sift_up运算大同小异，具体代码如下：

def insert(H,x,k):H.append(x)SIFT_UP(H,H.index(x),k)

在解决单源最短路径的问题的时候，会遇到对数据项中最小键值的数据项的删除操作,具体代码如下：

def deletemin(H,k):x=H[1]delete(H,1,k)return x

以下是对最短路径的具体操作，其思想与Dijkstra的思想基本一致，只是运用堆去对路径进行了选择。具体代码如下：

def shoerestpath(lengh,H,V):V.remove(1)Y = Va=[0]*mk=[0]*mfor y in range(2,m+1):if lengh[1][y]!=inf:a[y-1]=lengh[1][y]k[y-1]=a[y-1]insert(H,y,k)else:a[y-1]=infk[y-1]=a[y-1]print(k)for j in range(1,m):# y = k.index(H[1]) + 1# delete(H, 1)y = deletemin(H,k)if y in Y:Y.remove(y)Y=Yfor w in range(1,m+1):if lengh[y][w]!=inf and w in Y:if a[y-1]+lengh[y][w]<a[w-1]:a[w-1]=a[y-1]+lengh[y][w]k[w-1]=a[w-1]print(k)if w not in H:insert(H,w,k)else:SIFT_UP(H,H.index(w),k)print(a)

完整代码如下：

from math import inf
def SIFT_UP(H,i,k):done = Falseif i==1:return print(f"节点{i}为根")while i>1 or not done:if i>1:a=int(H[i]-1)b=int(H[i // 2]-1)if k[a]<k[b]:H[i],H[i//2]=H[i//2],H[i]else: done =Truei = i//2else:break
def SIFT_down(H,i,k):a =  int(H[i] - 1)b = int(H[i // 2] - 1)c = int(H[i+1]-1)n = len(H)-1done = Falseif 2*i>n:print(f"节点{i}是叶子")while 2*i<=n or not done:i=2*iif i+1<=n and k[c]<k[a]:i=i+1if i<=n:#H[i]在列表内的时候，执行以下语句if k[b]>k[a]:H[i],H[i//2]=H[i//2],H[i]else:done = True
def delete(H,i,k):x=H[i]n=len(H)-1y=H[n]del H[n]if i==n+1:print("完成")if i==len(H):print(k)else:H[i]=yif k[y-1]>=k[x-1]:SIFT_UP(H,i,k)else:SIFT_down(H,i,k)
def insert(H,x,k):H.append(x)SIFT_UP(H,H.index(x),k)
def deletemin(H,k):x=H[1]delete(H,1,k)return x
def shoerestpath(lengh,H,V):V.remove(1)Y = Va=[0]*mk=[0]*mfor y in range(2,m+1):if lengh[1][y]!=inf:a[y-1]=lengh[1][y]k[y-1]=a[y-1]insert(H,y,k)else:a[y-1]=infk[y-1]=a[y-1]print(k)for j in range(1,m):# y = k.index(H[1]) + 1# delete(H, 1)y = deletemin(H,k)if y in Y:Y.remove(y)Y=Yfor w in range(1,m+1):if lengh[y][w]!=inf and w in Y:if a[y-1]+lengh[y][w]<a[w-1]:a[w-1]=a[y-1]+lengh[y][w]k[w-1]=a[w-1]print(k)if w not in H:insert(H,w,k)else:SIFT_UP(H,H.index(w),k)print(a)
if __name__ == '__main__':lengh = [[0,0,0,0,0,0,0],[0,0,1,12,inf,inf,inf],[0,inf,0,9,3,inf,inf],[0,inf,inf,0,inf,5,inf],[0,inf,inf,4,0,13,15],[0,inf,inf,inf,inf,0,4],[0,inf,inf,inf,inf,inf,0]]H=[inf]V={1,2,3,4,5,6}m=len(V)shoerestpath(lengh,H,V)

基于Python的堆优化单源最短路径

本文主要是本人对堆优化单源最短路径中堆的一些理解，如有需要还会发布对单源最短路径的解释。参考书目：Algorithms Design Techniques and Analysis【沙特】M.H.Alsuwaiyel，如有错误欢迎留言指出，谢谢。

在了解最小堆的特性之后，首先，要实现堆运算Sift_up,假定对于某个i，其键值变成了小于父节点的键值元素，这样就违反了最小堆的特性，所以要通过Sift_up，把这个不符合最小堆特性的数据项重新转移到二叉树的合适位置，以此修复最小堆的特性。具体代码如下：

def SIFT_UP(H,i,k):#H为堆，k为堆中数据项的键值done = Falseif i==1:return print(f"节点{i}为根")while i>1 or not done:if i>1:#在堆中，忽略H[0],因此在此代码中H[0]=inf,为避免H[i//2-1]取到inf，在此加入限制条件a=int(H[i]-1)b=int(H[i // 2]-1)if k[a]<k[b]:H[i],H[i//2]=H[i//2],H[i]else: done =Truei = i//2else:break

其次，在实际运算中，我们也会遇到存储在H中的数据项的键值有小于其子节点的键值的，这样也不符合最小堆的特性，因此需要用堆运算Sift_down,把这个不合适的数据项重新转移到合适的位置。具体代码如下：

def SIFT_down(H,i,k):a =  int(H[i] - 1)b = int(H[i // 2] - 1)c = int(H[i+1]-1)n = len(H)-1done = Falseif 2*i>n:print(f"节点{i}是叶子")while 2*i<=n or not done:i=2*iif i+1<=n and k[c]<k[a]:i=i+1if i<=n:#H[i]在列表内的时候，执行以下语句if k[b]>k[a]:H[i],H[i//2]=H[i//2],H[i]else:done = True

在实际运算中，我们可能需要对堆中的一些数据项进行删除处理，为了使删除数据项之后的堆依旧符合最小堆的特性，就需要对堆进行Sift_up或Sift_down运算，直到满足堆的特性。具体的删除代码如下：

"""要从大小为n的堆H中删除第i个元素，可以先用第n个元素替代第i个元素，然后将堆的大小减1"""
def delete(H,i,k):x=H[i]n=len(H)-1y=H[n]del H[n]if i==n+1:print("完成")if i==len(H):print(k)else:H[i]=yif k[y-1]>=k[x-1]:SIFT_UP(H,i,k)else:SIFT_down(H,i,k)

在实际运算中也要运用到插入堆的运算，插入堆与堆的Sift_up运算大同小异，具体代码如下：

def insert(H,x,k):H.append(x)SIFT_UP(H,H.index(x),k)

在解决单源最短路径的问题的时候，会遇到对数据项中最小键值的数据项的删除操作,具体代码如下：

def deletemin(H,k):x=H[1]delete(H,1,k)return x

以下是对最短路径的具体操作，其思想与Dijkstra的思想基本一致，只是运用堆去对路径进行了选择。具体代码如下：

def shoerestpath(lengh,H,V):V.remove(1)Y = Va=[0]*mk=[0]*mfor y in range(2,m+1):if lengh[1][y]!=inf:a[y-1]=lengh[1][y]k[y-1]=a[y-1]insert(H,y,k)else:a[y-1]=infk[y-1]=a[y-1]print(k)for j in range(1,m):# y = k.index(H[1]) + 1# delete(H, 1)y = deletemin(H,k)if y in Y:Y.remove(y)Y=Yfor w in range(1,m+1):if lengh[y][w]!=inf and w in Y:if a[y-1]+lengh[y][w]<a[w-1]:a[w-1]=a[y-1]+lengh[y][w]k[w-1]=a[w-1]print(k)if w not in H:insert(H,w,k)else:SIFT_UP(H,H.index(w),k)print(a)

完整代码如下：

from math import inf
def SIFT_UP(H,i,k):done = Falseif i==1:return print(f"节点{i}为根")while i>1 or not done:if i>1:a=int(H[i]-1)b=int(H[i // 2]-1)if k[a]<k[b]:H[i],H[i//2]=H[i//2],H[i]else: done =Truei = i//2else:break
def SIFT_down(H,i,k):a =  int(H[i] - 1)b = int(H[i // 2] - 1)c = int(H[i+1]-1)n = len(H)-1done = Falseif 2*i>n:print(f"节点{i}是叶子")while 2*i<=n or not done:i=2*iif i+1<=n and k[c]<k[a]:i=i+1if i<=n:#H[i]在列表内的时候，执行以下语句if k[b]>k[a]:H[i],H[i//2]=H[i//2],H[i]else:done = True
def delete(H,i,k):x=H[i]n=len(H)-1y=H[n]del H[n]if i==n+1:print("完成")if i==len(H):print(k)else:H[i]=yif k[y-1]>=k[x-1]:SIFT_UP(H,i,k)else:SIFT_down(H,i,k)
def insert(H,x,k):H.append(x)SIFT_UP(H,H.index(x),k)
def deletemin(H,k):x=H[1]delete(H,1,k)return x
def shoerestpath(lengh,H,V):V.remove(1)Y = Va=[0]*mk=[0]*mfor y in range(2,m+1):if lengh[1][y]!=inf:a[y-1]=lengh[1][y]k[y-1]=a[y-1]insert(H,y,k)else:a[y-1]=infk[y-1]=a[y-1]print(k)for j in range(1,m):# y = k.index(H[1]) + 1# delete(H, 1)y = deletemin(H,k)if y in Y:Y.remove(y)Y=Yfor w in range(1,m+1):if lengh[y][w]!=inf and w in Y:if a[y-1]+lengh[y][w]<a[w-1]:a[w-1]=a[y-1]+lengh[y][w]k[w-1]=a[w-1]print(k)if w not in H:insert(H,w,k)else:SIFT_UP(H,H.index(w),k)print(a)
if __name__ == '__main__':lengh = [[0,0,0,0,0,0,0],[0,0,1,12,inf,inf,inf],[0,inf,0,9,3,inf,inf],[0,inf,inf,0,inf,5,inf],[0,inf,inf,4,0,13,15],[0,inf,inf,inf,inf,0,4],[0,inf,inf,inf,inf,inf,0]]H=[inf]V={1,2,3,4,5,6}m=len(V)shoerestpath(lengh,H,V)