您现在的位置是：首页 > Python 当前栏目 python实现堆 Python 2023-03-02 14:05:07 时间 import random #用于测试 class Heap(object):#这是个最小值堆 def __init__(self,mylist=None): self.__size=0 self.__heaplist=[] #两种建堆方式，一种是一个一个插，另一种是直接载入一个列表 if type(mylist)==type(self.__heaplist): self.__heaplist=mylist self.__size = len(mylist) self.build_heap() def is_leaf(self,pos):#因为是完全二叉树，是否是叶子结点很容易写出 return (pos>=self.__size//2)and(pos<self.__size) def left_child(self,pos): return 2*pos+1 def right_child(self,pos): return 2*pos+2 def parent(self,pos): return pos//2 def get_size(self): return self.__size #这个函数的用法是把某一结点通过沉降达到适合的位置，最小值堆的话比子节点大就下沉 def shift_down(self,pos): while(not self.is_leaf(pos)): min_child=self.left_child(pos) rc=self.right_child(pos) if (rc<self.__size)and(self.__heaplist[rc]<self.__heaplist[min_child]): min_child=rc if self.__heaplist[pos]<=self.__heaplist[min_child]: return self.__heaplist[pos],self.__heaplist[min_child]=self.__heaplist[min_child],self.__heaplist[pos] pos=min_child #这个就是shift_down的逆用法了 def push_up(self,pos): while (pos !=0) and (self.__heaplist[pos]<self.__heaplist[self.parent(pos)]): self.__heaplist[pos],self.__heaplist[self.parent(pos)]=self.__heaplist[self.parent(pos)],self.__heaplist[pos] pos=self.parent(pos) def build_heap(self): if self.__size == 0: return child=self.__size-1 pnt=self.parent(child) for i in range(pnt,-1,-1):#范围是pnt到0的循环 self.shift_down(i) def insert(self,data): pos=self.__size self.__size+=1 self.__heaplist.append(data) self.push_up(pos) def remove_first(self): if self.__size ==0: return self.__heaplist[self.__size-1],self.__heaplist[0]=self.__heaplist[0],self.__heaplist[self.__size-1] self.__size-=1 if(self.__size !=0): self.shift_down(0) return self.__heaplist.pop() def remove_pos(self,pos): if self.__size ==0: return if pos==self.__size-1: self.__size-=1 else: self.__heaplist[self.__size - 1], self.__heaplist[pos] = self.__heaplist[pos], self.__heaplist[self.__size - 1] self.__size-=1 #只可能是push_up或者shift_down,又或者不动 self.push_up(pos) if self.__size!=0: self.shift_down(pos) return self.__heaplist.pop() list1=list(range(10)) random.shuffle(list1) print(list1) #两种建堆 h=Heap(list1) for i in range(10): print(h.remove_first()) for i in range(10): h.insert(i) print(' ') for i in range(10): print(h.remove_first()) #剩下的功能就自己尝试吧 输出： [4, 5, 6, 8, 0, 2, 7, 1, 9, 3] 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 本文地址： python实现堆 相关文章 python 数据库错误 Python膨胀操作 python plt 绘图 python 转义字符 Python连接Mysql python连接mysql python连接mysql [Python] ord() 函数 python 解析器 python io模块 python str 类 python环境安装 Python之模块 Python函数(2) Python 赋值机制 python 99乘法表 Python - Lambda表达式 笔记：Python函数 python函数笔记 Python Date & Time
