学习笔记 | 《算法导论》之从入门到放弃(3)
2023-04-18 14:52:57 时间
算法导论打卡3,主要内容:堆排序
第六章 堆排序
堆
- 二叉堆是一个数组,它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除了最底层外,该树是完全充满的,而且是从左向右填充。
- 表示堆的数组A包括两个属性:A.length(通常)给出数组元素的个数,A.heap-size表示有多少个堆元素存储在该数组中。也就是说虽然A[1..A.length]可能都存有数据,但只有A[1..A.heap-size]中存放的是堆的有效元素,这里0≤A.heap-size≤A.length。树的根节点是A[1],这样给定一个结点的下标i,我们很容易计算得到它的父结点,左孩子和右孩子的下标:
def parent(i):
return i//2
def left(i):
return 2*i
def right(i):
return 2*i+1
- 二叉堆可以分为两种形式:最大堆和最小堆。在这两种堆中,结点的值都要满足堆的性质。区别在于:
- 最大堆中,最大堆性质是指除了根以外的所有结点i都要满足:A[PARENT(i)]≥A[i],即在任一子树中,该子树所包含的所有结点的值都不大于该子树根节点的值。
- 最小堆中,最小堆性质是指除了根以外的所有结点i都要满足:A[PARENT(i)]≤A[i]
- 在堆排序算法中,我们使用最大堆。最小堆通常用于构造优先队列。
- 如果把堆看成一棵树,我们定义一个堆中的结点的高度是该节点到叶结点最长简单路径上
边的数目
。既然一个包含n个元素的堆可以看作是一颗完全二叉树,那么该堆的高度是O(lgn)
- 堆结构上的一些基本操作的运行时间至多与树的高度成正比,即时间复杂度为O(lgn).
维护堆的性质
- 通过让A[i]的值在最大堆中“逐级下降”,从而使得以下标i为根结点的子树重新遵循最大堆的性质:
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=len(A)-1
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
- 对于一个高为h的结点来说,max_heapify的时间复杂度是O(h)。
建堆
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
- 完整代码:
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=A[0]
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
if __name__ == "__main__":
#数组的第一个位置存储堆元素个数,并用于占位
A=[9,50, 16, 30, 10, 60, 90, 2, 80, 70]
build_max_heap(A)
for i in range(1,A[0]+1):
print(A[i])
堆排序算法
- 因为数组的最大元素总是在根结点A[1]中,通过把它与A[n]进行互换,我们可以把该元素放到正确的位置上(如从小到大排列)
def max_heapify(A,i):
l,r=2*i,2*i+1
heap_size=A[0]
if(l<=heap_size and A[l]>A[i]):
largest=l
else:
largest=i
if(r<=heap_size and A[r]>A[largest]):
largest=r
if(largest!=i):
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest)
def build_max_heap(A):
#A[0]存储堆元数个数
for i in range(1,A[0]//2+1)[::-1]:
max_heapify(A,i)
def heapsort(A):
build_max_heap(A)
n=A[0]
for i in range(2,n+1)[::-1]:
temp=A[1]
A[1]=A[i]
A[i]=temp
A[0]-=1
max_heapify(A,1)
A[0]=n
if __name__=="__main__":
#数组的第一个位置存储堆元素个数,并用于占位
A=[9,50, 16, 30, 10, 60, 90, 2, 80, 70]
heapsort(A)
for i in range(1,A[0]+1):
print(A[i])
- heapsort的时间复杂度是O(nlgn),因为每次调用build_max_heap的时间复杂度是O(n),而n-1次调用max_heapify,每次的时间是O(lgn)。
优先队列
- 优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的值,称为关键字。
- 一个最大优先队列支持以下操作:
- insert(S,x):把元素x插入集合S中。
- maximum(S):返回S中具有最大关键字的元素。
- extract-max(S):去掉并返回S中具有最大关键字的元素。
- increase-key(S,x,k):将元素x的关键字值增加到k,这里假设k的值不小于x的原关键字值。
- 最小优先队列同理
- 实现:
def heap_maximum(A):
return A[1]
def heap_extract_max(A):
heap_size=len(A)-1
if(heap_size<1):
raise IndexError("heap underflow")
Max=A[1]
A[1]=A[heap_size]
heap_size-=1
max_heapify(A,1)
return Max
def heap_increase_key(A,i,key):
if(key<A[i]):
raise Exception,"new key is small than current key"
A[i]=key
while(i>1 and A[parent[i]]<A[i]):
temp=A[i]
A[i]=A[parent[i]]
A[parent[i]]=temp
i=parent[i]
def max_heap_insert(A,key):
heap_size+=1
A[heap_size]=float('-inf')
heap_increase_key(A,heap_size,key)
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击