在我刚开始学习数据结构的时候，二叉堆是我最恶心的结构。 看起来像树的不是树，而是上浮下沉，头大。 最后读了labuladong先生的文章，好像终于明白了一点。 写文章做记录。
堆这个数据结构在实际问题中很常用，最直接的是堆排序和优先级队列。 很多语音提供堆实现的库函数直接调用就可以了，但是作为基础数据结构应该把握原理和实现。
开始构建堆的本质是完全二叉树，要求所有节点都有两个子节点(大顶堆或小顶堆)。 这一步很容易理解。 接下来，在实际情况下，我们将把它堆叠成一个数组。 你可能知道如何用数组存储完整的二叉树，但这是一模一样的。 通过此方法，可以使用数组的索引快速计算子节点和父节点。
例如，在数组arr中，将树根放在arr[1]的位置。 **请注意，此处的索引为1，而不是0。 0的位置暂时不用，我们的山从1开始。 *对于一个节点arr[n]，左右的孩子分别是arr[2*n]和arr[2*n 1]。 可以通过以下方式计算节点索引
#父节点索引defparent(root ) :#root-intreturn root *//2(左子索引defleft ) root ) :#root-intreturnroot ) 如果你还是不太清楚，请看我偷的这张图。 (摘录： http://labuladong.git book.io/algo/Shu-ju-Jie-Gou-Xi-lie/er-cha-dui-dui ) ) ) )
[导出外链图像失败。 源站可能有防盗链机制。 我们建议您保存并直接上传图片。 (img-lqR2MMui-1599480415647 ) 3359 github.com/xhy 13770656533/Xiao _ Bao _ plao ) ]
我们做插入和删除，说最头痛的地方，山的上浮和下沉操作。 我在看数据结构书的时候一直不知道他们的区别，后来觉得应该看看作用再谈实现。 把这个问题看得浅一点可能会好一点。
那就从作用说起。 这两种操作都是为了在堆栈结构被破坏时调整为正常结构，但是什么样的操作会破坏堆栈结构呢？ 插入和删除元素只有两个操作。
这个时候再强调堆栈的特征。一般来讲，在堆中插入元素只能插在堆底，而删除元素只能删堆顶元素首先，让我们以一个大堆为例来看看代码。 然后，你可能会知道为什么需要两种调整堆的方法。
####插入操作###definsert(key ) :#堆大小加1N=1# )在最后一个heap(n )=key )中添加新元素使其浮动到正确位置swim(n ) ####删除操作# # 减少一个堆大小，heap[1]，heap[N]=heap[N]，heap[1]heap[N]=NoneN-=1#将当前索引1中的元素下沉到正确的位置，然后sink [1] retrete
对于下沉操作，如果节点a小于其子节点(之一)，则a不属于父节点。 你应该下车。 在下面更大的节点上创建父节点。 也就是说，交换a及其大子节点。 重复此操作直到a到达正确的位置。
对于上浮操作，节点a大于其父节点，所以a不应该成为子节点，而应该调换父节点，自己成为父节点。 也就是说，节点a和他的父节点被调换。 重复此操作直到a到达正确的位置。
两者看似等效，但区别在于上浮用于插入操作，下沉用于删除操作。
####上浮###defswim(k ) :## ) k-int )最多上浮到堆栈顶部while(k1andheap[parent ) : )，第k要素是其他父节点下沉###defsink ) k ) 3:# k-int#最大下沉到炉底while(left(k )=N ) 3360#否则更换大孩子#首先左边的孩子大older=left(k 大小if right(k ) k ) NAND heap [ older ] heap [ right ] k [ : older=right ] )进行比较
分代码也就几行。感觉也没有那么难嘛。最后我试试把细节都加上，写一个完整的二叉堆代码，感兴趣的可以参考一下 class Heap: def __init__(self,K): # K->int 表示堆中最大元素数量 self.heap = [None] * (K+1) self.MaxSize = K self.N = 0 #父节点索引 def parent(self,root):#root->int return root // 2 #左孩子索引 def left(self,root):#root->int return root * 2 #右孩子索引 def right(self,root):#root->int return root * 2 + 1 def swim(self,k): # k->int # 最多浮到浮到堆顶 while(k>1 and self.heap[self.parent(k)]<self.heap[k]): #如果第k元素比他父节点大，就把他和他的父节点交换 self.heap[self.parent(k)] , self.heap[k] = self.heap[k] , self.heap[self.parent(k)] k = self.parent(k) def sink(self,k): # k->int # 最多沉到堆底 while(self.left(k)<=self.N): # 与两个孩子节点比较，如果大于两个孩子则不需要下沉，否则和较大的孩子交换 # 先假设左孩子比较大 older = self.left(k) # 然后判断是否存在右孩子，比较一下大小 if self.right(k)<=self.N and self.heap[older] < self.heap[self.right(k)]: older = self.right(k) # 如果比两个都大，直接结束 if self.heap[older] < self.heap[k]: break self.heap[k] , self.heap[older] = self.heap[older] , self.heap[k] k = older def insert(self,key): # Key->int key表示插入的值，搞简单一点就用int好了 if self.N<self.MaxSize: self.N+=1 #把新元素加到最后 self.heap[self.N] = key #把他上浮到正确位置 self.swim(self.N) return True else: return False def delTop(self): if self.N>0: #对顶元素为最大或最小元素 res = self.heap[1] #把这个元素交换到最后,删除之，堆的大小减一 self.heap[1] , self.heap[self.N] = self.heap[self.N] , self.heap[1] self.heap[self.N] = None self.N-=1 #把现在位于索引1的元素下沉到正确位置 self.sink(1) return res else: return -99999 总结前面思路整理了那么多，但最后完整实现出来也费了不少劲，这个算法还是建议大家自己实现一遍比较好。
堆的本质是一个完全二叉树，所以用数组来存放。
可能上浮和下沉操作会有一点绕，多看几遍起始不难。上浮对应插入元素，下沉对应删除堆顶元素。
参考文章labuladong算法小抄：二叉堆详解实现优先队列