Python自定义二叉堆类

野性酷女 2022-02-19 08:53 219阅读 0赞

**二叉堆有两种**：最小成员key排在队首的称为“最小堆(min heap)”；最大key排在队首的是“最大堆(max heap)”，这是一种优先队列的实现方式。

优先队列的出队(Dequeue)操作和队列一样，都是从队首出队。但在优先队列内部，数据项的次序是由它们的“优先级”来确定的：有最高优先级的数据项排在队首,而优先级最低的数据项则排在队尾。这样，优先队列的入队(Enqueue)操作就需要将数据项挤到队列前方。

**完全二叉树**：指每个内部节点都有两个子节点，最多可有一个节点例外。

如果完全树的节点在列表中的位置为p(p>0)，那么其左子节点的位置就为2p，右子节点的位置就为2p+1。

**找任意节点的父节点的方法**：若节点在列表中的位置为n，那么其父节点的位置就是n//2。

**堆次序**：是指堆中任意一个节点x，其父节点p中的key(节点值)均小于或等于x中的key。

# 自定义最小堆类
    class BinHeap(object):
    	# 构造二叉堆
    	def __init__(self):
    		# 表首下标为0的项并没有用到，但为了后面代码可以用到简单的整数乘除法，仍保留它
    		self.heapList = [0]			
    		self.currentSize = 0
    
    	# 上浮函数，i为节点位置，判断新节点是否比父节点小，若小则新节点交换上浮以保证堆次序
    	def percUp(self, i):
    		while i // 2 > 0:				#若父节点的位置大于0，则循环
    			if self.heapList[i] < self.heapList[i // 2]:	#若子节点值小于父节点值，则交换位置
    				self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
    			i = i // 2 					#更新当前节点位置，判断是否需要继续上浮
    
    	# 插入函数，添加新节点
    	def insert(self, k):
    		self.heapList.append(k)			#向堆中插入新节点
    		self.currentSize += 1 			#更新新节点位置
    		self.percUp(self.currentSize)	#检查新节点是否需要上浮，以维持堆次序
    
    	# 下沉函数，i为节点位置，判断子节点是否比父节点小，若小则父节点交换下沉以保证堆次序
    	def percDown(self, i):
    		# 若i*2<=当前节点位置(最后一个节点)，说明待测节点有子节点，则循环
    	    while (i * 2) <= self.currentSize:	
    	        mc = self.minChild(i)		#获取i的最小子节点位置
    	        if self.heapList[i] > self.heapList[mc]:	#若i的值>其最小子节点值，则交换位置
    	        	self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
    	        i = mc 						#更新待检测下沉节点位置，判断是否需要继续下沉
    	
    	# 获取最小子节点位置
    	def minChild(self, i):
    	    if i * 2 + 1 > self.currentSize:#i的右子节点位置>当前节点位置(最后一个节点)，则
    	        return i * 2 				#返回左子节点位置，因为i没有右子节点
    	    else:							#若i有右子节点，则
    	        if self.heapList[i * 2] < self.heapList[i * 2 + 1]:	#若i的左子节点值<右子节点值，则
    	            return i * 2 			#返回左子节点位置
    	        else:
    	            return i * 2 + 1 		#返回右子节点位置
    
    	# 删除最小节点
    	def delMin(self):
    	    retval = self.heapList[1]		#获取最小节点，即根节点
    	    # 以下4行代码是为了维持堆结构和堆次序
    	    self.heapList[1] = self.heapList[self.currentSize]	#将当前节点，即最后一个节点赋值给根节点，不能直接删除根节点，因为要维持堆结构
    	    self.heapList.pop()				#删除堆最后一个节点，因为此节点值已交换给了根节点
    	    self.currentSize -= 1 			#当前节点位置减1，因为删除了一个节点
    	    self.percDown(1)				#检查新的根节点是否需要下沉，以维持堆次序
    	    return retval 					#返回删除的最小节点
    
    	# 无序列表构建二叉堆
    	def buildHeap(self, alist):
    		self.currentSize = len(alist)	#获取列表最后一个位置
    		self.heapList = [0] + alist[:]	#列表0位置添加0元素，便于后续计算
    		i = len(alist) // 2 			#获取最后一个节点的父节点位置
    		while i > 0:
    			self.percDown(i)			#判断父节点是否需要下沉
    			i = i -1 					#将待检测节点位置更新为上一个节点位置
    
    bh = BinHeap()							#实例化最小堆类
    bh.buildHeap([9,5,6,2,3])				#无序列表构建最小堆
    print(bh)
    print(bh.delMin())						#删除当前最小节点
    print(bh.delMin())
    print(bh.delMin())
    bh.insert(7)							#添加新节点
    print(bh.delMin())
    print(bh.delMin())

**结果为：**

<__main__.BinHeap object at 0x00000000026FF630>
    2
    3
    5
    6
    7