首页 / 算法 / 堆、堆排序

堆、堆排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了堆、堆排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1822字，纯文字阅读大概需要3分钟。

内容图文

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
实现一个最大堆：
技术分享图片 技术分享图片 
                         1
                        import
                         random

                         2
                         3
                        def
                         main(args):

                         4     a = []
 5for i in range(100):
 6         a.append(random.randint(1,100))
 7print(a)
 8for i in range((100-1)//2,-1,-1):
 9        max_heapify(a,i)
10print(a)
11return 0
12131415def max_heapify(a,i):
16     left_child = 2 * i + 1
17     right_child = 2 * i + 2
18     large_index = i
19if left_child < len(a) and a[left_child] > a[large_index]:
20         large_index = left_child
21if right_child < len(a) and a[right_child] > a[large_index]:
22         large_index = right_child
23if large_index != i:
24         tmp = a[i]
25         a[i] = a[large_index]
26         a[large_index] = tmp
27        max_heapify(a,large_index)
282930if__name__ == ‘__main__‘:
31import sys
32     sys.exit(main(sys.argv))
最大堆实现

 

 

 

堆排序思想：

　　1.首先使欲排序数组（下标从0到n）变成一个最大堆；

　　2.将数组的第一个元素与最后一个元素做交换，此时最后一个元素为数组中最大的元素。

　　3.继续对欲排序数组（下标从0到n-1）进行第1、2步操作，每次操作后将最大堆的第一个元素与第n-1个元素交换。

　　4.重复以上操作直至未排序数组长度为1，排序完毕。

堆排序时间复杂度：Θ(nlgn)

技术分享图片 技术分享图片 
                         1
                        import
                         random

                         2
                         3
                        def
                         main(args):

                         4     a = []
 5for i in range(100):
 6         a.append(random.randint(1,100))
 7print(a)
 8for i in range(len(a)-2):
 9for j in range((len(a)-1-i)//2,-1,-1):
10             max_heapify(a,j,len(a)-i)
11         tmp = a[0]
12         a[0] = a[len(a)-i-1]
13         a[len(a)-i-1] = tmp
14print(a)
15return 0
1617def max_heapify(a,i,k):
18     left_child = 2 * i + 1
19     right_child = 2 * i + 2
20     large_index = i
21if left_child < k and a[left_child] > a[large_index]:
22         large_index = left_child
23if right_child < k and a[right_child] > a[large_index]:
24         large_index = right_child
25if large_index != i:
26         tmp = a[i]
27         a[i] = a[large_index]
28         a[large_index] = tmp
29        max_heapify(a,large_index,k)
3031if__name__ == ‘__main__‘:
32import sys
33     sys.exit(main(sys.argv))
堆排序

 

 

 

原文：https://www.cnblogs.com/wdl1078390625/p/9876364.html

内容总结

以上是互联网集市为您收集整理的堆、堆排序全部内容，希望文章能够帮你解决堆、堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1140108.html

来源：【匿名】