代码实现
# 二叉堆实现 # 采用“完全二叉树”的结构近似实现“平衡”的二叉树 # 对于完全二叉树，使用单个列表就可以实现完全树，如果节点在列表中的下标为p，其左节点下标为2p，右节点下标为2p+1；节点n的父节点为n//2 # 最小堆实现 class BinHeap: def __init__(self): self.heapList = [0] self.currentSize = 0 def percUp(self, i): while i // 2 > 0: # 如果新插入的值小于根节点值，进行替换 if self.heapList[i] < self.heapList[i // 2]: tmp = self.heapList[i] self.heapList[i] = self.heapList[i // 2] self.heapList[i // 2] = tmp # 逐层对比 i = i // 2 def insert(self, k): # 先将数值加入最后位置 self.heapList.append(k) self.currentSize += 1 # 调整到正确位置 self.percUp(self.currentSize) def percDown(self, i): # 不断向下进行对比 while (i * 2) <= self.currentSize: # 返回左子树或者右子树的位置 mc = self.minChild(i) # 如果根节点值大于子节点值，进行替换 if self.heapList[i] > self.heapList[mc]: tmp = self.heapList[i] self.heapList[i] = self.heapList[mc] self.heapList[mc] = tmp # 逐层对比 i = mc def minChild(self, i): # 是否存在右子树，不存在则返回左子树位置 if i * 2 + 1 > self.currentSize: return i * 2 else: # 如果左子树值小于右子树值，返回左子树位置；否则返回右子树位置 if self.heapList[i * 2] < self.heapList[i * 2 + 1]: return i * 2 else: return i * 2 + 1 def delMin(self): # 删除操作：将最后一个元素和第一个元素进行替换，再删除第一个元素，再跑一遍percDown进行调整 retval = self.heapList[1] self.heapList[1] = self.heapList[self.currentSize] self.currentSize -= 1 self.heapList.pop() self.percDown(1) return retval def bulidHeap(self, alist): # 需要自上而下进行构建，不是一个叠加过程，而是一个递归过程 # 再调整上层元素时，并不需要同下层所有元素作比较，只需要比较其中一个分支。同时这又是一个递归过程； # 生成二叉堆需要O(n)，关键在于对于许多buildHeap操作而言，树的高度要比logN要小 i = len(alist) // 2 self.currentSize = len(alist) self.heapList = [0] + alist while i > 0: self.percDown(i) # 自下而上进行对比 i -= 1
简单应用
Python中有函数将数组转化为最小堆，转化时间复杂度为O(n)
heapq.heapify(q) # Python提供了最小堆的实现函数，时间复杂度为O(n) d, x, y = heapq.heappop(q) heapq.heappush(q, (-diff(x + 1, y + 1), x + 1, y + 1)) # 插入新数据
例题
class Solution: def smallestK(self, arr: List[int], k: int) -> List[int]: if k == 0: return list() hp = [-x for x in arr[:k]] heapq.heapify(hp) for i in range(k, len(arr)): if -hp[0] > arr[i]: heapq.heappop(hp) heapq.heappush(hp, -arr[i]) ans = [-x for x in hp] return ans
