最大堆最小堆操作——python_最大堆转化成最小堆

刚讲完堆的一系列基本内容，把涉及的知识点整理下，看课本81-88页自行对照复习。

1. 堆heap，通常是一个可以被看做一棵树的数组对象。
2. 堆的性质：（1）是轶可完全二叉树；（2）某个节点的值总是大于或小于子节点
3. 相关的操作有用VB或C++实现的，其它的请自行百度，我们采用python完成
4. 算法开始，已知条件：序列A = [45, 36, 18, 53, 72, 30, 48, 93, 15, 35]，如下图所示，利用我们课本上的算法buildHeap如何将序列A转化为一个堆呢？
   
5. 注意构造的时候，从堆树的叶子节点开始，按照自底向上逐层处理每个节点，保证节点的堆化过程不重复。叶子节点不用说，符合条件不用处理，那就从第一个有叶子的分支节点开始处理，也就是mid=len(A)//2，观察上图可知mid=10//2=5,也即是索引为5的节点开始处理，正好是第一个有叶子的节点72，其它的类似这类节点有53，18，36，45都要检查是否满足最大堆特性，不满足就拉下马，降低它的级别，直到堆根节点进行调整后，整个树就变成了一个堆。教材上初始化堆的时候加了个0，是模仿Python的heapq库函数来设计的，就是为了比较节点索引使用的。

The initial seq is [0, 45, 36, 18, 53, 72, 30, 48, 93, 15, 35]:
1

6. 检查72这个节点的左孩子的大小，也就是通过maxChild来找72这个节点最大的孩子节点，没找到35<72，所以72不变，mid递减=4，看下图：
   
7. 接下来找mid=4,也即53这个节点，发现左孩子93>53,则53下沉，两个互换下位置，这里要注意53拉下马之后，53的索引变成了8，这个时候仍然要递归索引8到最大堆化函数中检查是否满足最大堆条件，什么时候停止呢？假设索引为i,则判断下2*i是否小于等于序列长度即可。见下图࿱