网站建设课程有哪些收获,今天上午北京发生了什么,店铺推广怎么做,工业设计专业介绍本文简要总结堆的概念。
更新#xff1a;2023 / 8 / 20 数据结构 | 堆 堆概念方法插入步骤 删除步骤 示例大根堆堆插入删除堆排序 代码实现Python大根堆1.2. heapq 小根堆1.2. heapq 参考链接 堆
概念
如果谈到堆排序#xff0c;那么必然要说说什么是 大根堆 max heap 和 …本文简要总结堆的概念。
更新2023 / 8 / 20 数据结构 | 堆 堆概念方法插入步骤 删除步骤 示例大根堆堆插入删除堆排序 代码实现Python大根堆1.2. heapq 小根堆1.2. heapq 参考链接 堆
概念
如果谈到堆排序那么必然要说说什么是 大根堆 max heap 和 小根堆 min heap 1。
max heap 若根节点存在左右子节点那么根节点的值大于或等于左右子节点的值 是根结点大于或者等于左右子节点的二叉树min heap 若根节点存在左右子节点那么根节点的值小于或等于左右子节点的值 是根结点x小于或者等于左右子节点的二叉树
那么我们可以总结出关于 max heap 和 min heap 的结论
堆是一颗完全二叉树min heap 的根节点是堆中最小值 max heap 的根节点是堆中最大值堆适合采用顺序存储 方法
堆最重要的两个方法就是 插入 和 删除 方法。 插入
将一个元素插入到堆中使之依然成为一个堆。 步骤
将元素插入到堆的尾部查看每个子树是否符合大小根堆的特点。若不符合则将节点逐层向上调整根和叶子节点的位置直至从该节点的父节点出发到根节点是一个有序序列直到所有节点都满足条件最终依然构成一个堆。 删除
堆在删除元素时只可以删除根节点然后使剩下的节点依然成为一个堆。 步骤
删除根节点用堆中最后元素进行填充查看每个子树是否符合大小根堆的特点。若不符合则进行调整直至所有节点都满足条件。 示例
堆的构建过程其实就是构建一个符合大根堆或者小根堆的完全二叉树那么就可以使用顺序表来进行存储。 大根堆
下面举例说明堆的构建过程 将无序序列 [49, 38, 65, 97, 76, 13, 27, 40] 构建大根堆。 堆 插入 49 插入 38 插入 65 因为要建立 max heap49 和 65 不符合大根堆的特点对其进行调整。调整后如下所示 插入 97 97 和 38 发生冲突进行调整 插入 76 76 和 65 发生冲突进行调整 插入 13 插入 27 插入 40 40 和 38 发生冲突进行调整 至此max heap 建立完成。可以看出根节点是最大值。 插入
在上面的基础上向 max heap 插入节点 99。
插入 99 99 和 40 发生冲突进行调整 99 和 76 发生冲突再次进行调整 99 仍然和 97 存在冲突再次进行调整 至此所有节点都符合堆的特性99 被成功插入 max heap。 删除
在上面的基础上因为只能删除根节点所以删除 max heap 的 99。
找到堆中最后的节点 40 删除根节点 99根节点被删除后由最后的节点 40 进行补位。 此时的根节点 40 并不大于或等于左右子节点。因此寻找此时左右子节点中的最大值 97 与此时的根节点 40 互换以进行调整 此时的节点 40 并不大于或等于左子节点 76。因此寻找此时节点 40 与 76 进行互换 至此所有节点都符合堆的特性99 被成功从 max heap 删除。 堆排序
堆排序是如何实现的呢 堆排序其实就是堆的删除过程。每次删除的都是堆的根节点删除后再进行调整使得剩下的节点还是堆然后再删除根节点。重复进行。直至堆中只有一个元素时便可直接输出。那么删除过程中产生的这个序列即是一个有序序列 2。 同样以上面的例子为例来看看堆排序是如何实现的
删除 99 删除 99 的过程可参考上面的 删除 部分的内容。在删除 99 后剩下的元素构成的堆如下所示 删除 97 剩下的元素构成的堆如下所示 删除 76 剩下的元素构成的堆如下所示 删除 65 剩下的元素构成的堆如下所示 删除 49 剩下的元素构成的堆如下所示 删除 40 剩下的元素构成的堆如下所示 删除 38 剩下的元素构成的堆如下所示 删除 27 剩下的元素构成的堆如下所示 至此堆中仅剩一个元素 13。 所以最后排序后的序列为 [99, 97, 76, 65, 49, 40, 38, 27, 13]排序完成。 代码实现
Python
大根堆
1.
以无序序列 [49, 38, 65, 97, 76, 13, 27, 4099] 为例
def maxheap(arr, end):print( * 20 max heapify )height int((end1)/ 2 - 1)print(f{height:20}: {height})for root in range(height, -1, -1):while True:child root * 2 1print(f{root:20}: {root}\n{child:20}: {child}\n{end:20}: {end})if child end:print(f- * 20 f child {child} end {end}, exit loop)breakif child1 end and arr[child] arr[child1]:print(f- * 20 f child1 {child 1} end {end} and arr[child] {arr[child]} arr[child1] {arr[child 1]})child child 1print(f{child now:20}: {child})if arr[root] arr[child]:print(f- * 20 f arr[root] {arr[root]} arr[child] {arr[child]}, root {root} child {child})arr[root], arr[child] arr[child], arr[root]root childprint(f- * 20 f arr[root] {arr[root]} arr[child] {arr[child]}, root {root} child {child} now)else:print(f- * 20 f arr[root] {arr[root]} arr[child] {arr[child]}, root {root} child {child}, exit loop)breakreturn arrdef sortheap(arr, end):for i in range(end, 0, -1):arr[0], arr[i] arr[i], arr[0]maxheap(arr, i-1)return arrif __name__ __main__:a [49, 38, 65, 97, 76, 13, 27, 40, 99]print(f排序前\n{a})print(- * 100 max heapify )a maxheap(a, len(a)-1)print(f大根堆\n{a})print(- * 100 sort heap )a sortheap(a, len(a)-1)print(f堆排序\n{a})输出信息如下所示
排序前
[23, 15, 30, 38, 65, 97, 40, 99]
---------------------------------------------------------------------------------------------------- max heapify max heapify
height : 3
root : 3
child : 7
end : 7
-------------------- arr[root] 38 arr[child] 99, root 3 child 7
-------------------- arr[root] 38 arr[child] 38, root 7 child 7 now
root : 7
child : 15
end : 7
-------------------- child 15 end 7, exit loop
root : 2
child : 5
end : 7
-------------------- arr[root] 30 arr[child] 97, root 2 child 5
-------------------- arr[root] 30 arr[child] 30, root 5 child 5 now
root : 5
child : 11
end : 7
-------------------- child 11 end 7, exit loop
root : 1
child : 3
end : 7
-------------------- arr[root] 15 arr[child] 99, root 1 child 3
-------------------- arr[root] 15 arr[child] 15, root 3 child 3 now
root : 3
child : 7
end : 7
-------------------- arr[root] 15 arr[child] 38, root 3 child 7
-------------------- arr[root] 15 arr[child] 15, root 7 child 7 now
root : 7
child : 15
end : 7
-------------------- child 15 end 7, exit loop
root : 0
child : 1
end : 7
-------------------- arr[root] 23 arr[child] 99, root 0 child 1
-------------------- arr[root] 23 arr[child] 23, root 1 child 1 now
root : 1
child : 3
end : 7
-------------------- child1 4 end 7 and arr[child] 38 arr[child1] 65
child now : 4
-------------------- arr[root] 23 arr[child] 65, root 1 child 4
-------------------- arr[root] 23 arr[child] 23, root 4 child 4 now
root : 4
child : 9
end : 7
-------------------- child 9 end 7, exit loop
大根堆
[99, 65, 97, 38, 23, 30, 40, 15]
---------------------------------------------------------------------------------------------------- sort heap max heapify
height : 2
root : 2
child : 5
end : 6
-------------------- child1 6 end 6 and arr[child] 30 arr[child1] 40
child now : 6
-------------------- arr[root] 97 arr[child] 40, root 2 child 6, exit loop
root : 1
child : 3
end : 6
-------------------- arr[root] 65 arr[child] 38, root 1 child 3, exit loop
root : 0
child : 1
end : 6
-------------------- child1 2 end 6 and arr[child] 65 arr[child1] 97
child now : 2
-------------------- arr[root] 15 arr[child] 97, root 0 child 2
-------------------- arr[root] 15 arr[child] 15, root 2 child 2 now
root : 2
child : 5
end : 6
-------------------- child1 6 end 6 and arr[child] 30 arr[child1] 40
child now : 6
-------------------- arr[root] 15 arr[child] 40, root 2 child 6
-------------------- arr[root] 15 arr[child] 15, root 6 child 6 now
root : 6
child : 13
end : 6
-------------------- child 13 end 6, exit loopmax heapify
height : 2
root : 2
child : 5
end : 5
-------------------- arr[root] 40 arr[child] 30, root 2 child 5, exit loop
root : 1
child : 3
end : 5
-------------------- arr[root] 65 arr[child] 38, root 1 child 3, exit loop
root : 0
child : 1
end : 5
-------------------- arr[root] 15 arr[child] 65, root 0 child 1
-------------------- arr[root] 15 arr[child] 15, root 1 child 1 now
root : 1
child : 3
end : 5
-------------------- arr[root] 15 arr[child] 38, root 1 child 3
-------------------- arr[root] 15 arr[child] 15, root 3 child 3 now
root : 3
child : 7
end : 5
-------------------- child 7 end 5, exit loopmax heapify
height : 1
root : 1
child : 3
end : 4
-------------------- child1 4 end 4 and arr[child] 15 arr[child1] 23
child now : 4
-------------------- arr[root] 38 arr[child] 23, root 1 child 4, exit loop
root : 0
child : 1
end : 4
-------------------- child1 2 end 4 and arr[child] 38 arr[child1] 40
child now : 2
-------------------- arr[root] 30 arr[child] 40, root 0 child 2
-------------------- arr[root] 30 arr[child] 30, root 2 child 2 now
root : 2
child : 5
end : 4
-------------------- child 5 end 4, exit loopmax heapify
height : 1
root : 1
child : 3
end : 3
-------------------- arr[root] 38 arr[child] 15, root 1 child 3, exit loop
root : 0
child : 1
end : 3
-------------------- arr[root] 23 arr[child] 38, root 0 child 1
-------------------- arr[root] 23 arr[child] 23, root 1 child 1 now
root : 1
child : 3
end : 3
-------------------- arr[root] 23 arr[child] 15, root 1 child 3, exit loopmax heapify
height : 0
root : 0
child : 1
end : 2
-------------------- child1 2 end 2 and arr[child] 23 arr[child1] 30
child now : 2
-------------------- arr[root] 15 arr[child] 30, root 0 child 2
-------------------- arr[root] 15 arr[child] 15, root 2 child 2 now
root : 2
child : 5
end : 2
-------------------- child 5 end 2, exit loopmax heapify
height : 0
root : 0
child : 1
end : 1
-------------------- arr[root] 15 arr[child] 23, root 0 child 1
-------------------- arr[root] 15 arr[child] 15, root 1 child 1 now
root : 1
child : 3
end : 1
-------------------- child 3 end 1, exit loopmax heapify
height : 0
root : 0
child : 1
end : 0
-------------------- child 1 end 0, exit loop
堆排序
[15, 23, 30, 38, 40, 65, 97, 99]2. heapq
参考这里 3
import heapqa [49, 38, 65, 97, 76, 13, 27, 40, 99]
print(f{排序前:20}: {a})print(- * 50 min heapify )
heapq.heapify(a)
print(f{小根堆:20}: {a})print(- * 50 max heapify )
newa [(-i, a[i]) for i in range(len(a))]
heapq.heapify(newa)
print(f{新小根堆:20}: {newa})
maxheap list()
while newa:_, s heapq.heappop(newa)print(f_, s: {_}, {s})maxheap.append(s)
print(f{大根堆:20}: {maxheap})输出信息如下所示
排序前 : [49, 38, 65, 97, 76, 13, 27, 40, 99]
-------------------------------------------------- min heapify
小根堆 : [13, 38, 27, 40, 76, 65, 49, 97, 99]
-------------------------------------------------- max heapify
新小根堆 : [(-8, 99), (-7, 97), (-6, 49), (-3, 40), (-4, 76), (-5, 65), (-2, 27), (-1, 38), (0, 13)]
_, s: -8, 99
_, s: -7, 97
_, s: -6, 49
_, s: -5, 65
_, s: -4, 76
_, s: -3, 40
_, s: -2, 27
_, s: -1, 38
_, s: 0, 13
大根堆 : [99, 97, 49, 65, 76, 40, 27, 38, 13]小根堆
1.
以无序序列 [49, 38, 65, 97, 76, 13, 27, 4099] 为例
def minheap(arr, start, end):height int((end1)/ 2 - 1)for root in range(height, -1, -1):while True:child root * 2 1if child end:breakif child-1 start and arr[child] arr[child-1]:child child-1if arr[root] arr[child]:arr[root], arr[child] arr[child], arr[root]root childelse:breakreturn arrdef sortheap(arr, start, end):for i in range(end, 0, -1):arr[0], arr[i] arr[i], arr[0]minheap(arr, 0, i-1)return arrif __name__ __main__:a [49, 38, 65, 97, 76, 13, 27, 40, 99]print(f排序前\n{a})print(- * 50 min heapify )a minheap(a, 0, len(a)-1)print(f小根堆\n{a})print(- * 50 sort heap )arr sortheap(a, 0, len(a)-1)print(f堆排序\n{a})输出信息如下所示
排序前
[49, 38, 65, 97, 76, 13, 27, 40, 99]
-------------------------------------------------- min heapify
小根堆
[13, 27, 38, 40, 76, 65, 97, 49, 99]
-------------------------------------------------- sort heap
堆排序
[99, 97, 76, 65, 49, 40, 38, 27, 13]2. heapq
参考这里 3
import heapqa [49, 38, 65, 97, 76, 13, 27, 40, 99]
print(f{排序前:20}: {a})print(- * 50 min heapify )
heapq.heapify(a)
print(f{小根堆:20}: {a})print(- * 50 min heapify )
newa [(i, a[i]) for i in range(len(a))]
heapq.heapify(newa)
print(f{新小根堆:20}: {newa})
minheap list()
while newa:_, s heapq.heappop(newa)print(f_, s: {_}, {s})minheap.append(s)
print(f{小根堆:20}: {minheap})输出信息如下所示
排序前 : [49, 38, 65, 97, 76, 13, 27, 40, 99]
-------------------------------------------------- min heapify
小根堆 : [13, 38, 27, 40, 76, 65, 49, 97, 99]
-------------------------------------------------- min heapify
新小根堆 : [(0, 13), (1, 38), (2, 27), (3, 40), (4, 76), (5, 65), (6, 49), (7, 97), (8, 99)]
_, s: 0, 13
_, s: 1, 38
_, s: 2, 27
_, s: 3, 40
_, s: 4, 76
_, s: 5, 65
_, s: 6, 49
_, s: 7, 97
_, s: 8, 99
小根堆 : [13, 38, 27, 40, 76, 65, 49, 97, 99]参考链接
#todo: 关于 Python 标准库 heapq 的 大根堆/最大堆的 API~ 浅谈大根堆小根堆以及堆排序python实现 ↩︎ Python 堆排序 ↩︎ python用heapq模块构建大根堆 ↩︎ ↩︎
