python实现堆（最大堆、最小堆、最小最大堆）

(资料图片)

1. 最大堆

class MaxHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_max(self):        if not self.heap:            return None        return self.heap[0]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_max(self):        if not self.heap:            return None        max_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down(0)        return max_item    def _heapify_up(self, i):        while i > 0 and self.heap[i] > self.heap[self.parent(i)]:            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]            i = self.parent(i)    def _heapify_down(self, i):        max_index = i        left = self.left_child(i)        if left < len(self.heap) and self.heap[left] > self.heap[max_index]:            max_index = left        right = self.right_child(i)        if right < len(self.heap) and self.heap[right] > self.heap[max_index]:            max_index = right        if i != max_index:            self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]            self._heapify_down(max_index)if __name__ == "__main__":    max_heap = MaxHeap()    max_heap.insert(1)    max_heap.insert(2)    max_heap.insert(0)    max_heap.insert(8)    print(max_heap.get_max())

复制

2. 最小堆

class MinHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_min(self):        if not self.heap:            return None        return self.heap[0]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_min(self):        if not self.heap:            return None        min_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down(0)        return min_item    def _heapify_up(self, i):        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]            i = self.parent(i)    def _heapify_down(self, i):        min_index = i        left = self.left_child(i)        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:            min_index = left        right = self.right_child(i)        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:            min_index = right        if i != min_index:            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]            self._heapify_down(min_index)

复制

3. 最小-最大堆

最小-最大堆的性质是：树中偶数层的每个节点都小于它的所有后代，而树中奇数层的每个节点都大于它的所有后代。

用途 双端优先级队列

class MinMaxHeap:    def __init__(self):        self.heap = []    def parent(self, i):        return (i - 1) // 2    def left_child(self, i):        return 2 * i + 1    def right_child(self, i):        return 2 * i + 2    def get_min(self):        if not self.heap:            return None        return self.heap[0]    def get_max(self):        if not self.heap:            return None        if len(self.heap) == 1:            return self.heap[0]        if len(self.heap) == 2:            return self.heap[1] if self.heap[1] > self.heap[0] else self.heap[0]        return self.heap[1] if self.heap[1] > self.heap[2] else self.heap[2]    def insert(self, item):        self.heap.append(item)        self._heapify_up(len(self.heap) - 1)    def extract_min(self):        if not self.heap:            return None        min_item = self.heap[0]        last_item = self.heap.pop()        if self.heap:            self.heap[0] = last_item            self._heapify_down_min(0)        return min_item    def extract_max(self):        if not self.heap:            return None        max_item = self.get_max()        max_index = self.heap.index(max_item)        self.heap[max_index] = self.heap[-1]        self.heap.pop()        if max_index < len(self.heap):            self._heapify_down_max(max_index)        return max_item    def _heapify_up(self, i):        if i == 0:            return        parent = self.parent(i)        if self.heap[i] < self.heap[parent]:            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]            self._heapify_up_max(parent)        else:            self._heapify_up_min(i)    def _heapify_up_min(self, i):        grandparent = self.parent(self.parent(i))        if i > 2 and self.heap[i] < self.heap[grandparent]:            self.heap[i], self.heap[grandparent] = self.heap[grandparent], self.heap[i]            self._heapify_up_min(grandparent)    def _heapify_up_max(self, i):        grandparent = self.parent(self.parent(i))        if i > 2 and self.heap[i] > self.heap[grandparent]:            self.heap[i], self.heap[grandparent] = self.heap[grandparent], self.heap[i]            self._heapify_up_max(grandparent)    def _heapify_down_min(self, i):        while True:            min_index = i            left = self.left_child(i)            if left < len(self.heap) and self.heap[left] < self.heap[min_index]:                min_index = left            right = self.right_child(i)            if right < len(self.heap) and self.heap[right] < self.heap[min_index]:                min_index = right            if i != min_index:                self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]                i = min_index            else:                break    def _heapify_down_max(self, i):        while True:            max_index = i            left = self.left_child(i)            if left < len(self.heap) and self.heap[left] > self.heap[max_index]:                max_index = left            right = self.right_child(i)            if right < len(self.heap) and self.heap[right] > self.heap[max_index]:                max_index = right            if i != max_index:                self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]                i = max_index            else:                break

复制

在这个实现中，MinMaxHeap类代表一个min-max堆，包含一个list堆，用于存放堆中的元素。 parent、left_child 和right_child 方法分别返回节点的父节点、左子节点和右子节点的索引。 get_min 方法返回堆中的最小元素，get_max 方法返回堆中的最大元素。 insert 方法将一个元素插入到堆中并维护堆属性。 extract_min 方法从堆中移除最小元素并保持堆属性。 extract_max 方法从堆中移除最大元素并保持堆属性。

_heapify_up、_heapify_up_min、_heapify_up_max、_heapify_down_min 和 _heapify_down_max 方法用于维护最小-最大堆属性。 _heapify_up 在向堆中插入元素后调用，以确保元素位于正确的位置。 _heapify_up_min 和 _heapify_up_max 由 _heapify_up 调用以维护最小-最大堆属性。 _heapify_down_min 和 _heapify_down_max 分别被 extract_min 和 extract_max 调用，以维护 min-max 堆属性。

关键词 :

科技

python实现堆（最大堆、最小堆、最小最大堆）

最小-最大堆的性质是：树中偶数层的每个节点都小于它的所有后代，而树中奇数层的每个节点都大于它的所有...

腾讯云 04-03 20:18:59

python实现堆（最大堆、最小堆、最小最大堆）

最小-最大堆的性质是：树中偶数层的每个节点都小于它的所有后代，而树中奇数层的每个节点都大于它的所有...

腾讯云 04-03 20:18:59

羚锐制药荣登中成药企业TOP100榜单第36位:快播报

3月28日，以“品牌引领，传承创新，推动中药产业高质量发展”为主题，由中国中药协会主办的第三届中国中...

大河报·豫视频 04-03 19:13:23

羚锐制药荣登中成药企业TOP100榜单第36位:快播报

3月28日，以“品牌引领，传承创新，推动中药产业高质量发展”为主题，由中国中药协会主办的第三届中国中...

大河报·豫视频 04-03 19:13:23

全球观点：西南证券：给予朗新科技买入评级

西南证券股份有限公司王湘杰近期对朗新科技进行研究并发布了研究报告《利润短期承压，双轮驱动复苏在途...

证券之星 04-03 19:11:06

全球观点：西南证券：给予朗新科技买入评级

西南证券股份有限公司王湘杰近期对朗新科技进行研究并发布了研究报告《利润短期承压，双轮驱动复苏在途...

证券之星 04-03 19:11:06

资讯推荐:羊肉块怎么做好吃又嫩（炖羊肉最忌讳两种佐料）

最佳答案羊肉清洗干净后切块，加入适量姜丝、葱花、辣椒粉、孜然粉，生抽、盐、淀粉，抓匀腌制15分钟。...

互联网 04-03 18:17:24

资讯推荐:羊肉块怎么做好吃又嫩（炖羊肉最忌讳两种佐料）

最佳答案羊肉清洗干净后切块，加入适量姜丝、葱花、辣椒粉、孜然粉，生抽、盐、淀粉，抓匀腌制15分钟。...

互联网 04-03 18:17:24

【热闻】武强县气象台发布大风蓝色预警【Ⅳ级/一般】

武强县气象台发布大风蓝色预警【Ⅳ级 一般】

二三里资讯 04-03 18:19:47

【热闻】武强县气象台发布大风蓝色预警【Ⅳ级/一般】

武强县气象台发布大风蓝色预警【Ⅳ级 一般】

二三里资讯 04-03 18:19:47

中药配方颗粒行业市场规模 中药配方颗粒行业市场销量分析|环球聚焦

中药配方颗粒的出现是中药发展到一定程度的结果，从神农尝百草开始，中药经过数千年的演变发展，中药理...

互联网 04-03 18:20:22

中药配方颗粒行业市场规模 中药配方颗粒行业市场销量分析|环球聚焦

中药配方颗粒的出现是中药发展到一定程度的结果，从神农尝百草开始，中药经过数千年的演变发展，中药理...

互联网 04-03 18:20:22

当前最新：卫星可以网购了 包邮上太空大市场将至吗 卫星互联网行业深度分析及发展前景预测报告

这个星期，一批国产商用卫星产品在电商平台上架，面向大众销售，最低折后百万元起。用透明的价格在公开...

中研普华集团、央视财经、中研网 04-03 18:16:53

当前最新：卫星可以网购了 包邮上太空大市场将至吗 卫星互联网行业深度分析及发展前景预测报告

这个星期，一批国产商用卫星产品在电商平台上架，面向大众销售，最低折后百万元起。用透明的价格在公开...

中研普华集团、央视财经、中研网 04-03 18:16:53

童车行业市场规模有多大 童车行业发展机遇分析_当前观点

随着三胎政策的开放，儿童经济明显升温，儿童消费市场增长态势加速，越来越多的投资者也看到了儿童项目...

中研网 互联网 04-03 18:18:11

童车行业市场规模有多大 童车行业发展机遇分析_当前观点

随着三胎政策的开放，儿童经济明显升温，儿童消费市场增长态势加速，越来越多的投资者也看到了儿童项目...

中研网 互联网 04-03 18:18:11

全球热头条丨工业废气处理产业发展现状 工业废气处理产业发展趋势预测

工业废气，是指企业厂区内燃料燃烧和生产工艺过程中产生的各种排入空气的含有污染物气体的总称。这些废...

互联网 04-03 18:10:37

全球热头条丨工业废气处理产业发展现状 工业废气处理产业发展趋势预测

工业废气，是指企业厂区内燃料燃烧和生产工艺过程中产生的各种排入空气的含有污染物气体的总称。这些废...

互联网 04-03 18:10:37

微动态丨中国宠物用品行业市场评估 中国宠物用品行业市场消费规模分析

目前我国宠物消费主要集中在北京、上海和广州，这些地区经济发达，人们消费观念先进，生活节奏快。但相...

互联网 04-03 18:02:49

微动态丨中国宠物用品行业市场评估 中国宠物用品行业市场消费规模分析

目前我国宠物消费主要集中在北京、上海和广州，这些地区经济发达，人们消费观念先进，生活节奏快。但相...

互联网 04-03 18:02:49

在华持续萎靡，全球却勇夺第三，现代汽车为何“西升东降”？

2022年现代汽车再度夺下全球销量第三名，位居丰田和大众之后。然而，其全球销售表现却有喜有忧，西升东...

西游社 04-03 17:42:22

在华持续萎靡，全球却勇夺第三，现代汽车为何“西升东降”？

2022年现代汽车再度夺下全球销量第三名，位居丰田和大众之后。然而，其全球销售表现却有喜有忧，西升东...

西游社 04-03 17:42:22

3亿国人有睡眠障碍，失眠到底该怎么治？:今头条

在豆瓣小组“睡吧-和失眠说再见”中，有超7万被失眠困扰的成员。“总是翻来覆去整夜睡不着”“一个晚上...

澎湃新闻 04-03 17:23:19

3亿国人有睡眠障碍，失眠到底该怎么治？:今头条

在豆瓣小组“睡吧-和失眠说再见”中，有超7万被失眠困扰的成员。“总是翻来覆去整夜睡不着”“一个晚上...

澎湃新闻 04-03 17:23:19

2023金属锂市场需求与未来发展态势分析

金属锂市场调研如何?随着近年西部人才引进方案的落实，大批高素质人才驻扎西部地区，以及新的盐湖提锂技...

百度百科 中研网 04-03 17:15:12

2023金属锂市场需求与未来发展态势分析

金属锂市场调研如何?随着近年西部人才引进方案的落实，大批高素质人才驻扎西部地区，以及新的盐湖提锂技...

百度百科 中研网 04-03 17:15:12

当前讯息：新型城镇化建设行业发展分析2023

城镇化是现代化的必由之路。党的二十大报告指出：“推进以人为核心的新型城镇化”。这是促进区域协调发...

国家发展改革委 人民网 04-03 17:11:58

当前讯息：新型城镇化建设行业发展分析2023

城镇化是现代化的必由之路。党的二十大报告指出：“推进以人为核心的新型城镇化”。这是促进区域协调发...

国家发展改革委 人民网 04-03 17:11:58

天天讯息：2023年中国酒吧行业发展现状分析

传统酒吧在极大程度上依赖纸质化的单据记录客户的消费信息、核算营业额等。为了加强日常管理，提高运营...

互联网 04-03 17:26:03

天天讯息：2023年中国酒吧行业发展现状分析

传统酒吧在极大程度上依赖纸质化的单据记录客户的消费信息、核算营业额等。为了加强日常管理，提高运营...

互联网 04-03 17:26:03

你的光照亮了我的世界作文600字_求 作文 ldquo 曾被我忽视的世界 rdquo

1、漫无目的的走在大街上，已是深秋了，我无聊的拿脚踢着地上的落叶，“缓缓飘落的枫叶像思念，为何挽回...

互联网 04-03 16:59:08

你的光照亮了我的世界作文600字_求 作文 ldquo 曾被我忽视的世界 rdquo

1、漫无目的的走在大街上，已是深秋了，我无聊的拿脚踢着地上的落叶，“缓缓飘落的枫叶像思念，为何挽回...

互联网 04-03 16:59:08

众安保险2022年承保盈利3.29亿元 境内总保费同比增长16.1%

综合成本率进一步下降至98 5%，其中，赔付率为55 2%，费用率为43 3%；实现承保盈利人民币3 29亿元，...

中国网财经 04-03 16:47:59

众安保险2022年承保盈利3.29亿元 境内总保费同比增长16.1%

综合成本率进一步下降至98 5%，其中，赔付率为55 2%，费用率为43 3%；实现承保盈利人民币3 29亿元，...

中国网财经 04-03 16:47:59

特朗普计划飞到纽约“自首”？​特朗普还能参与总统竞选吗?

自美国纽约曼哈顿大陪审团3月30日宣布将对美国前总统特朗普进行起诉后，相关消息便成为全球舆论关注焦点...

中国财投网 04-03 16:59:44

特朗普计划飞到纽约“自首”？​特朗普还能参与总统竞选吗?

自美国纽约曼哈顿大陪审团3月30日宣布将对美国前总统特朗普进行起诉后，相关消息便成为全球舆论关注焦点...

中国财投网 04-03 16:59:44

特朗普计划飞到纽约“自首”？特朗普为何被起诉?

自美国纽约曼哈顿大陪审团3月30日宣布将对美国前总统特朗普进行起诉后，相关消息便成为全球舆论关注焦点...

中国财投网 04-03 16:56:48

特朗普计划飞到纽约“自首”？特朗普为何被起诉?

自美国纽约曼哈顿大陪审团3月30日宣布将对美国前总统特朗普进行起诉后，相关消息便成为全球舆论关注焦点...

中国财投网 04-03 16:56:48

2023自来水行业供需格局 自来水行业发展现状分析|世界播报

自来水行业市场多大?我国水资源短缺问题严峻。2021年，我国水资源总量为29638 20亿立方米，人均水资源...

百度 04-03 16:15:14

2023自来水行业供需格局 自来水行业发展现状分析|世界播报

自来水行业市场多大?我国水资源短缺问题严峻。2021年，我国水资源总量为29638 20亿立方米，人均水资源...

百度 04-03 16:15:14