一个简单的堆的小例子 leetcode

序

python有一个专门的heap文件, import heap就可以了.
目的: 这里只是一个单纯的形成堆的例子,给一个list,将list堆化

思路

简爱说一代码的思路,代码参考B站( https://www.bilibili.com/video/av47196993?from=search&seid=17395044821033317472 )

首先堆是一个完全二叉树,根据完全二叉树的性质,我们可以找到一个节点的父亲节点和孩子节点:
parent = ( i - 1 ) / 2
c1 = 2i + 1
c2 = 2i + 2
如果是最大堆,那么所有节点都比他的孩子节点大,同理最小堆.
根据上面的性质,我们可以写一个函数,做局部堆化( heapfiy ,三个节点,一个父亲,两个孩子),但是只是单纯的比较交换后,会有一个问题,如果孩子节点交换上来,父亲节点下去,你不能保证,这个交换过后,原本的堆的性质依然存在,不会因为我的交换而打乱(见2),所以我们需要对交换后的节点进行再次堆化,如此递归下去,我称之为,为局部堆化擦屁股…
【一个简单的堆的小例子】好了,上面只是局部堆化,为了形成完整的堆,我们可以从下往上遍历,同样利用一个小trick,我们可以找到最后一个叶子节点的父亲节点,我们可以从这里开始,逐个遍历到根节点,对每一个进行堆化.

代码

''' 1.根据数据的先后顺序或重要程度等给数据编的号码 2.优先级队里的实现方式有多种，其中最高效的一种便是堆(heap) 3.完全二叉树: 根节点是i，那么它的左儿子=2*i，右儿子=2*i+1 4.堆的特点,对于任何子结构: parent > children'''# 数组实现 class MaxHeap:def swap(self,max,i):global treetemp = tree[max] tree[max] = tree[i] tree[i] = temp# 来历:堆化 # 从一个节点出发,保证其子结构成堆状,很明显,我们需要从下往上走 # 倒数第二层,局部堆化 + 擦屁股 def heapfiy(self,n,i): ''' :param tree: 表示一个完全二叉树 :param n: 树中的节点个数 :param i: 哪一个节点做heapfiy操作 :return: '''global tree# 递归出口 if( i >= n ): returnc1 = 2 * i + 1 c2 = 2 * i + 2 max = iif( c1 < n and tree[c1] > tree[max] ): max = c1 if( c2 < n and tree[c2] > tree[max]): max = c2if(max != i): self.swap(max,i) # 递归? self.heapfiy(n,max)def build_heap(self): global tree n = len(tree)print(tree) last_node = n - 1 last_parent = int(( last_node -1 )/2) print(last_parent)for i in range(last_parent,-1,-1): self.heapfiy(n,i)tree = [2,5,3,1,10,4]maxheap = MaxHeap()# [5, 10, 3, 1, 2, 4] maxheap.heapfiy(len(tree),0)print(tree)