迎中国建设银行网站,工业设计是学什么,手机网站分享,建设网站需要注册证书吗一、堆
1、堆的介绍 堆#xff08;heap#xff09;是一种满足特定的条件的完全二叉树#xff0c;主要可以分为大根堆和小根堆。
大根堆#xff08;max heap#xff09;#xff1a;任意节点的值大于等于其子节点的值。小根堆#xff08;min heap#xff09;#xff1…一、堆
1、堆的介绍 堆heap是一种满足特定的条件的完全二叉树主要可以分为大根堆和小根堆。
大根堆max heap任意节点的值大于等于其子节点的值。小根堆min heap任意节点的值小于等于其子节点的值。 由于堆作为完全二叉树的一个特例故其具有以下的特性
1、最深一层的节点靠左填充且前面所有层地节点均被填满。
2、将完全二叉树的根节点称为堆顶将底层最靠右的节点称为堆底。
3、对于大根堆/小根堆堆顶元素的值是最大/最小的。
2、堆的常用操作 需要指出的是许多编程语言提供的是优先队列priority queue这是一种抽象的数据结构定义为具有优先级排序的队列。 实际上堆通常用于实现优先队列大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看我们可以将“优先队列”和“堆”看作等价的数据结构。因此本书对两者不做特别区分统一称作“堆”。
import heapq# 初始化小顶堆
min_heap, flag [], 1
# 初始化大顶堆
max_heap, flag [], -1# Python 的 heapq 模块默认实现小顶堆
# 考虑将“元素取负”后再入堆这样就可以将大小关系颠倒从而实现大顶堆
# 在本示例中flag 1 时对应小顶堆flag -1 时对应大顶堆heapq.heappush(max_heap,flag * 1)
heapq.heappush(max_heap,flag * 3)
heapq.heappush(max_heap,flag * 2)
heapq.heappush(max_heap,flag * 5)
heapq.heappush(max_heap,flag * 4)# 获取堆顶元素
peek:int flag * max_heap[0]
print(f堆顶元素为{peek})size:int len(max_heap)
print(f堆的大小为{size})print(输出大顶堆为,end)
# 堆顶元素出堆会按照从大到小的顺序输出
for i in range(len(max_heap)):val flag * heapq.heappop(max_heap)print(val,end)print()
is_empty:bool not max_heap
print(f当前堆是否为空{is_empty})# 输入列表并建堆
min_heap:list[int] [1,3,2,5,4]
heapq.heapify(min_heap)
print(f小顶堆对应的列表为{min_heap})3、堆的实现 下文实现的是大顶堆若要将其转化为小顶堆则只需要将对应的大于等于改为小于等于即可。
3.1堆的存储与表示 在之前的二叉树章节中提到过完全二叉树非常适合用数组表示由于堆正好是一种完全二叉树所以我们用数组的形式存储堆。
当使用数组表示二叉树时元素代表节点值索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。
如图 8-2 所示给定索引 i 其左子节点的索引为 2i1 右子节点的索引为 2i2 父节点的索引为 (i−1)/2向下整除。当索引越界时表示空节点或节点不存在。 堆的基本存储就是如上所示查找当前节点i对应的左子节点右子节点以及其父节点都不过多讲述了与二叉树的数组存储一样还有求当前的堆顶元素堆的大小等都在3.4的代码中展示轻而易举就能看懂下面着重讲解一下堆的插入元素以及堆顶元素出堆的操作
3.2、堆的元素插入 给定一个任意元素要将其插入堆中首先应把这个元素放到堆底添加后由于是大顶堆需要判断新加入的元素是否破坏了原本的大顶堆的结构若破坏了新插入的元素值大于其父节点的值则需要从该节点开始从底向上进行堆化就是需要不断调整交换位置将新插入的节点与其父节点的值交换就这样一直操作直到越过根节点或遇到无需交换的节点时结束。
如下图12中的所示新插入元素7但其大于其父节点的值5所以先进行一步交换然后再把7与其父节点6进行比较仍大于继续交换最后判断7是否大于其父节点的值9很明显不大于则最后不交换7与9的值。 图1 图2 3.3、堆顶元素出堆 堆顶元素是完全二叉树的根节点也就是列表首元素若直接从列表中删除它那么会导致列表中所有结点的索引都会发生变化故会有以下的操作
首先交换堆顶元素与堆底元素也就是根节点与最右边的叶子节点。
然后交换完成后将堆底元素从列表中删除实际就是把原来的堆顶元素给删除了。
最后从根节点开始由顶到底进行堆化操作。
注意这里的堆化操作是由顶至底进行的在调整时需要把根节点与最大的子节点进行交换这样便会找到除了原本的头节点以外最大的元素也就是次大元素如此循环往复直到越过叶子节点或遇到无需交换的节点为止。
如图34所示要删除原来的堆顶元素9故需要先将堆顶元素9与堆底元素5交换位置然后直接将新的堆底元素删除接下来就需要堆化操作将元素5与其最大的子节点8交换再把元素5与其当前的最大的子节点7进行交换再把元素5与其最大的子节点6进行交换这样便交换完成元素6成为元素3和5的父节点整体满足了大顶堆。 图3 图4 3.4代码
class MaxHeap:def __init__(self,num:list[int]):# 将列表中的元素添加到堆中self.max_heap numdef left(self,i:int)-int:获取索引i节点的左子节点return 2 * i 1def right(self,i:int)-int:获取右子节点的索引return 2 * i 2def parent(self,i:int)-int:获取节点i的父亲节点索引return (i - 1) // 2 # 向下取整def peek(self)-int:获取堆顶元素return self.max_heap[0]def size(self)-int:堆的大小return len(self.max_heap)def push(self,val:int):元素入堆self.max_heap.append(val)# 从底至顶堆化self.sift_up(self.size() - 1)def swap(self,i:int,j:int):交换元素self.max_heap[i],self.max_heap[j] self.max_heap[j],self.max_heap[i]def sift_up(self,i:int):从节点i开始从底至顶堆化while True:# i节点的父节点p self.parent(i)if self.max_heap[i] self.max_heap[p] or p 0:breakself.swap(i,p)# 循环向上堆化i pdef pop(self)-int:堆顶元素出堆if self.size() 0:raise IndexError(堆为空)# 交换堆顶节点与堆底节点self.swap(0,self.size()-1)# 删除节点val self.max_heap.pop()self.sift_down(0)# 返回堆顶元素return valdef sift_down(self,i:int):while True:l, r, ma self.left(i),self.right(i),iif l self.size() and self.max_heap[l] self.max_heap[ma]:ma lif r self.size() and self.max_heap[r] self.max_heap[ma]:ma rif ma i:break# 交换两个节点self.swap(i,ma)# 循环向下堆化i ma 4、堆的常见应用
优先队列通常作为实现优先队列的首选数据结构其入队和出队操作的时间复杂度均为 O(log n) 而建堆操作为 O(n) 这些操作都非常高效。堆排序给定一组数据我们可以用它们建立一个堆然后不断地执行元素出堆操作从而得到有序数据。然而我们通常会使用一种更优雅的方式实现堆排序详见“堆排序”章节获取最大的k个元素这是一个经典的算法问题同时也是一种典型应用例如选择热度前 10 的新闻作为微博热搜选取销量前 10 的商品等。 二、建堆操作 在某些情况下我们希望使用一个列表的所有元素来创建一个堆这个过程被称为建堆操作。
1、借助入堆操作实现 先创建一个空堆然后依次对每一个元素执行入堆操作即先将元素添加至堆的尾部再对元素执行从底至顶堆化。且每当一个新的元素入堆堆的长度就要加1。由于元素的插入是按照从顶到底的方式插入的因此这种方式是自上而下构建的堆。
若每个元素的入堆操作时间复杂度为O(log n)那么建堆方法有n个元素的时间复杂度就为O(n log n)。
2、通过遍历堆化实现 这是一种实现更高效的建堆方法主要分为两步
首先将列表中的所有元素原封不动的添加到堆中此时堆还尚未能满足大根堆或小根堆的性质
然后倒序遍历堆层序遍历的倒序依次对每个非叶子节点执行从顶至底堆化操作。 三、Top-k问题
Question:给定一个长度为n的无序数组nums请返回数组中最大的k个元素。 对于该问题可以先介绍比较直接的思路解法再介绍比较更高的堆的解法。
解法1遍历/迭代 类似于选择排序的思路进行k轮遍历每轮找到当前nums中剩余的未排序的最大的元素时间复杂度为O(n*k)显然当kn时还比较使用但当k无限接近于n的时候时间复杂度与趋近于O(n^2)非常耗时。 解法2排序 可以先对数组排序然后根据排序的顺序截取k个元素即可但时间复杂度为O(n log n)显然这种做法有点冗余了我们并不需要一直求解到第n大的元素求解到第k大的元素即可。故我们只需要找出最大的k个元素即可以k为限制条件而不需要排序其他的元素。 解法3基于堆的解法 因为是需要返回前k个大的元素所以我们使用一个小根堆保证其堆顶的元素最小然后将数组的前k个元素分别入堆接着从第k1个元素开始若当前元素大于堆顶元素将堆顶元素出堆将当前元素入堆遍历完所有元素后堆中保存的就是最大的k个元素。
import heapqdef top_k_heap(nums:list[int],k:int)-list[int]:基于小顶堆查找数组中的最大的k个元素heap []for i in range(k):heapq.heappush(heap,nums[i])for i in range(k,len(nums)):if nums[i]heap[0]:heapq.heappop(heap)heapq.heappush(heap,nums[i])return heapnum [1,7,6,3,2,5]
l top_k_heap(num,4)
print(f前k个最大的元素为{l}) # output:前k个最大的元素为[3, 5, 6, 7]
总共执行了n轮入堆和出堆堆的最大长度为k因此时间复杂度为O(n log k)该方法的效率很高当k较小时时间复杂度趋于O(n)当k很大时时间复杂度不会超过O(n log n)。 四、交换两个元素值
方法1 在Python中可以通过元组解包或多重赋值来交换两个元素的值。
# 方法1
a,b 10,1
a,b b,a
方法2 添加中间变量这也是在一些其他编程语言中常会用到的思想。
a,b 10,1
tmp a
a b
b tmp
方法3 不使用中间变量或者是Python所自带的多重赋值那么使用算术运算和逻辑运算也同样可以实现两个元素值的交换。 3.1算术运算 算术运算就比如一些可以先是正运算再是逆运算的运算规则进行求解。
3.1.1加减法
# 加减法
a,b 10,1
a a b
b a - b
a a - b
3.1.2乘除法
# 乘除法
a,b 10,1
a a * b
b a / b
a a / b
方法4 使用逻辑运算符号异或
a,b 10,1
a a ^ b
b a ^ b
a a ^ b
