删除任意一个元素
修改任意一个元素
基本结构完全二叉树除了最后一层节点，上面所有节点都是满的
最后一层节点，从左到右依次排布
堆的特性每个根节点都小于等于或者大于等于他的左右儿子节点堆的存储使用一维数组存储。x的左儿子是2xx的右儿子是2x+例如：(此处为了方便数组下标从开始)操作原理及实现核心思想堆的两种操作方式（以小根堆为例，大根堆相反）down：当有一个较大（与它的两个儿子节点相比）的数进入堆时，比较它和它的两个儿子节点，如果两个儿子节点比它更小则它与最小的哪个儿子节点交换位置，直到不能再交换为止。up：当有一个较小的数进入堆时，它与它的头节点做比较，如果它比头节点还要小，则交换它和它的头节点。模拟操作
使用heap和size分别表示数组和数组的下标。(此处为了方便数组下标从开始)插入一个数：heap[++size]=x;up(size);即在末尾插入，然后执行up操作。求集合中的最小值：heap[]删除最小值：heap[]=heap[size];size--;down()即用最后一个元素覆盖第一个，然后去掉最后一个元素，最后把第一个元素down一遍。删除任意一个元素k：heap[k]=heap[size];size--;down[k]；up(k);即用最后一个元素覆盖将要删除的第k个元素，然后去掉最后一个元素，最后虽然执行了down(k)up(k)，但是这是因为我们不知道k是变大了，还是变小了，所以索性down和up都实现，但是其实只会执行一个（根据k变大或者变小）。修改任意一个元素k为x：heap[k]=x;down(k);up(k);即直接把值x赋到位置k。然后执行down，up就行了，和上面相同根据k的变大或者变小，down或者up只会执行一个。代码实现#n列整数，从小到大输出前m个。n,m=map(int,input().split())#下标从开始，所以序列头放一个元素0占位。nums=[0]+list(map(int,input().split()))size=ndefdown(x):#用i计算左右节点i=x#当左儿子存在并且小于根节点那么就把根节点给左儿子ifx*2=sizeandnums[x*2]nums:i=x*2ifx*2+=sizeandnums[x*2+]nums:i=x*2+#如果后面的根节点不是原来的了，#说明左右儿子里有比原根节点小的，#我们把原来的根节点和新的根节点交换ifi!=x:nums,nums[x]=nums[x],nums#并且一直执行down操作到不能down为止down(i)defup(x):#只需要比较当前节点是不是比他的父节点小，#如果小就把当前节点上移whilex//2andnums[x//2]nums[x]:nums[x//2],nums[x]=nums[x],nums[x//2]x=x//2#从倒数第二层开始往后down。foriinrange(n//2,0,-):down(i)res=[]foriinrange(m):#输出头节点print(nums[],end=)nums[]=nums[size]size-=down()预览时标签不可点收录于话题#个上一篇下一篇