南通网站定制方案,代理网页打不开,中山cms建站,佛山仿站定制模板建站先来看看什么是堆? 堆是一种图的树形结构#xff0c;被用于实现“优先队列”#xff08;priority queues#xff09;
注:优先队列是一种数据结构#xff0c;可以自由添加数据#xff0c;但取出数据时要从最小值开始按顺序取出。 在堆的树形结构中#xff0c…先来看看什么是堆? 堆是一种图的树形结构被用于实现“优先队列”priority queues
注:优先队列是一种数据结构可以自由添加数据但取出数据时要从最小值开始按顺序取出。 在堆的树形结构中各个顶点被称为“结点”node数据就存储在这些结点中堆中的每个结点最多有两个子结点 在堆中存储数据时必须遵守这样一条规则子结点必定大于父结点。因此最小值被存储在顶端的根结点中。从堆中取出数据时取出的是最上面的数据。这样堆中就能始终保持最上面的数据最小。同时由于最上面的数据被取出因此堆的结构也需要重新调整。 01 首先在堆中存储所有的数据并按降序来构建堆。 02 现在所有数据都存进堆里了。为了排序需要再从堆中把数据一个个取出来。注 从降序排列的堆中取出数据时会从最大的数据开始取所以将取出的数据反序输出排序就完成了。 03 首先取出根结点的数字7。 04 重新构造堆。 重构的规则请参考
[数据结构]图解堆结构及其代码实现-CSDN博客 05 同样地取出根结点的数字6将它放在右数第2个位置上。 06 重新构造堆。 07 重复上述操作直到堆变空为止。 08 排序中…… 09 从堆中取出了所有数字排序完成。 解说 堆排序一开始需要将n个数据存进堆里所需时间为Onlogn。排序过程中堆从空堆的状态开始逐渐被数据填满。由于堆的高度小于log2n所以插入1个数据所需要的时间为Ologn。 每轮取出最大的数据并重构堆所需要的时间为Ologn。由于总共有n轮所以重构后排序的时间也是Onlogn。因此整体来看堆排序的时间复杂度为Onlogn。 这样来看堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间On2都要短但由于要使用堆这个相对复杂的数据结构所以实现起来也较为困难。 一般来说需要排序的数据都存储在数组中。这次我们使用了堆这种数据结构但实际上这也相当于将堆嵌入到包含了序列的数组中然后在数组中通过交换数据来进行排序。具体来说就是让堆中的各结点和数组像下图这样呈对应关系。正如大家所见这可以说是强行在数组中使用了堆结构。 代码演示
def heapify(arr, n, i):# 初始化最大值的索引为当前节点largest i# 左子节点的索引left 2 * i 1# 右子节点的索引right 2 * i 2# 如果左子节点比当前节点大更新最大值索引if left n and arr[i] arr[left]:largest left# 如果右子节点比当前节点大更新最大值索引if right n and arr[largest] arr[right]:largest right# 如果最大值不是当前节点交换值并递归调整if largest ! i:arr[i], arr[largest] arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n len(arr)# 构建最大堆Max Heap# 从最后一个非叶子节点开始到根节点逐个进行堆调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐步取出最大元素并进行堆调整for i in range(n - 1, 0, -1):# 将当前最大值堆顶与未排序部分的最后一个值交换arr[i], arr[0] arr[0], arr[i]# 对剩余元素重新构建最大堆heapify(arr, i, 0)return arrarr [2, 6, 7,8, 9, 4, 10, 3, 5, 1]
sorted_arr heap_sort(arr)
print(sorted_arr)
结果:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
更详细的可以看这篇文章
[数据结构]图解堆结构及其代码实现-CSDN博客 文章来源:书籍《我的第一本算法书》
书籍链接:
我的第一本算法书 (豆瓣) (douban.com)
作者宫崎修一 石田保辉
出版社人民邮电出版社
ISBN9787115495242
本篇文章仅用于学习和研究目的不会用于任何商业用途。引用书籍《我的第一本算法书》的内容旨在分享知识和启发思考尊重原著作者宫崎修一和石田保辉的知识产权。如有侵权或者版权纠纷请及时联系作者。 ———————————————— 版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。 原文链接https://blog.csdn.net/jhghuhbb/article/details/139089141
