python实现堆(最大堆、最小堆、最小最大堆)|焦点讯息
2023-04-04 17:40:46 来源:腾讯云
(资料图)
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实现堆(最大堆、最小堆、最小最大堆)|焦点讯息
- 中企投资非洲对接会在京举办
- 环球热推荐:wifi密码忘了怎么办手机查看密码_wifi密码忘了怎么办
- 宝马美国Q1销量增长11.9%,其消费者车型喜好和中国有何不同?
- 创新赋能 砥砺深耕 阳光财险荣获《中国银行保险报》三项大奖
- 汤姆猫:股东王健因在被证监会行政处罚未满六个月期间内违规减持股份 收深交所监管函
- 国华人寿被罚49万,因财务数据不真实 当前关注
- 【疫情防控】口罩可以摘了吗?钟南山最新发声_全球热点
- 热讯:徐汇融媒滨江慢直播丨感受生活脉动 共赏四时风景
- 公告速递:招商普盛全球配置(QDII)基金2023年境外主要市场节假日暂停申购(含定期定额投资)和赎回业务
- 研究发现全球湿地甲烷排放加剧|天天动态
- 世界热议:芬兰“入约”,俄方公布应对措施
- 第三届消博会亮点抢先看 释放提振消费积极信号
- 杨丽萍孔雀舞被批不雅,男女贴身来回乱蹭,网友:这艺术欣赏不来
- WBG败给BLG,官博沦陷!粉丝喊话:Easyhoon下课!野辅打得太差了
- 1米86!22岁中锋将加盟申花,上赛季打进6球,有望参加亚运会|今日热文
- 贲门腺癌局部晚期能治愈吗_贲门腺癌可以治愈吗
- 电子元器件分销龙头上市,中电港借资本市场竞争力再上台阶
- 精准把脉、对症施策、示范攻坚——2023年上海高校实验室安全示范攻坚项目推进会顺利召开
- 中国核建:预计在十四五规划末期公司最高同时建设核电机组数量有可能达到4050台
- 华泰证券:从BloombergGPT看金融GPT机遇|天天快播
- 四月天宇开启浪漫甜蜜之旅:“织女”携流星雨闪亮登场_天天观速讯
- 9.39万元起售 最高9.99万元!长安CS35 PLUS畅享版上市|全球新要闻
- 姬松茸菇有什么功效,松姬茸有何功效什么人不能吃|热头条