python实现最大堆，最小堆和堆排序 电玩女神 2022-02-20 14:17 436阅读 0赞 **目录** 0.什么是堆 1.最大堆的实现 2.最小堆的实现 3.堆排序 ### 0.什么是堆 ### 小堆和大堆分为如下图： ![2018091712014232][] > 堆需要满足的条件： > > 1. 必须是二叉树，且必须是完全二叉树 > > 2. 各个父节点必须大于或小于左右结点， 其中最顶层的根结点必须是最大或者最小的 堆可以使用list实现，就是按照层序遍历顺序将每个节点上的值存放在数组中。父节点和子节点之间存在如下的关系： i 从0 开始 parent = (i-1) // 2; left = 2\*i + 1 ; right = 2\*(i+1) ### 1.最大堆的实现 ### > 堆使用数组的形式表示，不需要使用指针 ![20180917194848174][] > 2. 在堆中增加元素 ![20180917200043958][] > 3,删除根节点，并重建堆结构 ![20180917200108791][] #最大堆的实现 class MaxHeap(): def __init__(self, maxSize=None): self.maxSize = maxSize self.li = [None] * maxSize self.count = 0 def length(self): #求数组的长度 return self.count def show(self): if self.count <= 0: print('null') else: print(self.li[: self.count]) def add(self, value): if self.count >= self.maxSize: #判断是否数组越界 raise Exception('full') self.li[self.count] = value #将新节点增加到最后 self._shift_up(self.count) # 递归构建大堆 self.count += 1 def _shift_up(self, index): #往大堆中添加元素，并保证根节点是最大的值: #1.增加新的值到最后一个结点，在add实现； 2.与父节点比较，如果比父节点值大，则交换 if index > 0: parent = (index - 1) // 2 # 找到根节点 if self.li[index] > self.li[parent]: #交换结点 self.li[index], self.li[parent] = self.li[parent], self.li[index] self._shift_up(parent) #继续递归从底往上判断 def extract(self): #弹出最大堆的根节点，即最大值 #1.删除根结点，将最后一个结点作为更结点 ； 2.判断根结点与左右结点的大小，交换左右结点较大的 if not self.count: raise Exception('null') value = self.li[0] self.count -= 1 self.li[0] = self.li[self.count] #将最后一个值变为第一个 self._shift_down(0) return value def _shift_down(self, index): # 1.判断是否有左子节点并左大于根，左大于右；2.判断是否有右子节点，右大于根 left = 2 * index +1 right = 2 * index + 2 largest = index #判断条件 # 下面2个条件包含了，判断左右结点那个大的情况。如果为3， 4， 5,： 第一个判断条件使得largest=1，再执行第二个条件，则判断其左结点与右结点的大小 if left < self.length() and self.li[left] > self.li[largest]: largest = left if right < self.length() and self.li[right] > self.li[largest]: largest = right if largest != index: # 将 两者交换 self.li[index], self.li[largest] = self.li[largest], self.li[index] self._shift_down(largest) m = MaxHeap(10) import numpy as np np.random.seed(123) num = np.random.randint(100, size =10) #创建随机的10个数 print(m.length()) for i in num: m.add(i) m.show() print(m.length()) for i in range(5): print(m.extract(), end=' ,') ### 2.最小堆的实现 ### #构造最小堆 class MinHeap(): def __init__(self, maxSize=None): self.maxSize = maxSize self.array = [None] * maxSize self._count = 0 def length(self): return self._count def show(self): if self._count <= 0: print('null') print(self.array[: self._count], end=', ') def add(self, value): #增加元素 if self._count >= self.maxSize: raise Exception('The array is Full') self.array[self._count] = value self._shift_up(self._count) self._count += 1 def _shift_up(self, index): #比较结点与根节点的大小， 较小的为根结点 if index > 0: parent = (index - 1) // 2 if self.array[parent] > self.array[index]: self.array[parent], self.array[index] = self.array[index], self.array[parent] self._shift_up(parent) def extract(self): #获取最小值，并更新数组 if self._count <= 0: raise Exception('The array is Empty') value = self.array[0] self._count -= 1 #更新数组的长度 self.array[0] = self.array[self._count] #将最后一个结点放在前面 self._shift_down(0) return value def _shift_down(self, index): #此时index 是根结点 if index < self._count: left = 2 * index + 1 right = 2 * index + 2 #判断左右结点是否越界，是否小于根结点，如果是这交换 if left < self._count and right < self._count and self.array[left] < self.array[index] and self.array[left] < self.array[right]: self.array[index], self.array[left] = self.array[left], self.array[index] #交换得到较小的值 self._shift_down(left) elif left < self._count and right < self._count and self.array[right] < self.array[left] and self.array[right] < self.array[index]: self.array[right], self.array[index] = self.array[index], self.array[right] self._shift_down(right) #特殊情况： 如果只有做叶子结点 if left < self._count and right > self._count and self.array[left] < self.array[index]: self.array[left], self.array[index] = self.array[index], self.array[left] self._shift_down(left) mi = MinHeap(10) print() print('-------小顶堆----------') for i in num: mi.add(i) mi.show() print(mi.length()) for _ in range(len(num)): print(mi.extract(), end=', ') print() print(mi.length()) 参考：[https://blog.csdn.net/qq\_23869697/article/details/82735088][https_blog.csdn.net_qq_23869697_article_details_82735088] [https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/15\_%E5%A0%86%E4%B8%8E%E5%A0%86%E6%8E%92%E5%BA%8F/heap\_and\_heapsort/\#\_4][https_python-data-structures-and-algorithms.readthedocs.io_zh_latest_15_E5_A0_86_E4_B8_8E_E5_A0_86_E6_8E_92_E5_BA_8F_heap_and_heapsort_4] ### 3.堆排序 ### def maxHeapfy(alist, length, parent): left = 2 * parent + 1 right = 2 * parent + 2 largest = parent if left < length and alist[left] > alist[largest]: largest = left if right < length and alist[right] > alist[largest]: largest = right if largest != parent: alist[largest], alist[parent] = alist[parent], alist[largest] maxHeapfy(alist, length, largest) # 递归构建 def buildMaxHeap(alist): # 构建最大堆 n = len(alist) lastParent = (n-1) // 2 for i in range(lastParent, -1, -1): maxHeapfy(alist, n, i) def heapSort(alist): buildMaxHeap(alist) n = len(alist) for i in range(n-1, -1, -1): alist[0], alist[i] = alist[i], alist[0] # 将最大值放在最后面 maxHeapfy(alist, i, 0) return alist a = [30,50,57,77,62,78,94,80,84] print(a) print(heapSort(a)) alist = [2, 4, 1, 2, 5, 58, 45, 24, 67] print(heapSort(alist)) b = [random.randint(1,1000) for i in range(1000)] print(b) print(heapSort(b)) ### 项目推荐： ### **[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]** **[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]** **[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]** **[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]** **[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]** **[最全最详细数据结构与算法视频-【附课件和源码】][-]** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center] [2018091712014232]: /images/20220220/b8a5352c7bfd4bf3923f83a5f0202211.png [20180917194848174]: /images/20220220/f3974ee092874f699937e4c2d859ef2c.png [20180917200043958]: /images/20220220/ecc470e8724a4e8facc5eef9ddf56257.png [20180917200108791]: /images/20220220/f5feb2d95a88406bbb2a7eee67178074.png [https_blog.csdn.net_qq_23869697_article_details_82735088]: https://blog.csdn.net/qq_23869697/article/details/82735088 [https_python-data-structures-and-algorithms.readthedocs.io_zh_latest_15_E5_A0_86_E4_B8_8E_E5_A0_86_E6_8E_92_E5_BA_8F_heap_and_heapsort_4]: https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/15_%E5%A0%86%E4%B8%8E%E5%A0%86%E6%8E%92%E5%BA%8F/heap_and_heapsort/#_4 [2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q [2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect [Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect [Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect [Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect [-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20220220/0ff106327b2e49d19716d642b8bbcab2.png
还没有评论，来说两句吧...