每个节点的值都大于或等于其左右子节点的值，其中根节点（亦为堆顶）的值是堆里所有节点中最大（小）的，称为大（小）顶堆，又称大（小）根堆。

　　大顶堆要求每个非叶子节点的值既大于或等于左子树的值，又大于或等于右子树的值，小顶堆则反之。大顶堆结构如下图所示。

　　大（小）顶堆的插入

　　不失一般性，这里只讨论大顶堆。大顶堆的插入遵循任意非叶子节点的值大于或等于左右两个子节点值的原则（左右两个节点值之间没有先后顺序)。具体算法逻辑如下图所示（以二叉树和数组方式分别演示，图中的二叉树并非二叉排序树，而是父节点值大于左右两个节点值的大顶树)。

　　大顶堆实际操作的是一个数组，为了清晰起见，画成二叉树进行对比。数组中没有指针，只能用2×n＋1代表左节点索引，2×n＋2代表右节点索引(n为当前节点下标)。插入的新节点时，如果要找到父节点的下标需要用下列公式：

　　(1)当前节点下标为奇数n（n%2=1）时：父节点下标=(n-1)/2。

　　(2)当前节点下标为偶数n（n%2=0）时：父节点下标=(n-2)/2。

Python可以用统一公式(n-1)//2（n>0）计算。

　　程序代码：

　　运行结果：

　　练习题１：修改上例代码，变成小顶堆。

　　分层显示

　　大（小） 顶堆所对应的树的形状和完全二叉树一样的，所以可以用二叉堆的分层显示。

　　程序代码：

　　运行结果：

　　练习２：把上例改为小顶堆，也用分层遍历。

　　节点删除

　　方法一：在堆的列表中查找到该节点，截取该节点前的列表作为新堆，该点后的数据逐个加入新堆中。

　　程序代码：

　　方法二：方法一逻辑上简单，代码也不多，但如果是删除前面的元素，运算量就和重新构建一个大（小）堆差不多，没有实用价值。堆是一个数组或列表，那么删掉一个元素后，这个堆的长度就缩小1。因此，先用一个临时变量last缓存最后一个元素，然后堆缩小1。如果被删除节点是叶节点，用last代替，如是非递归调用则要调整，完成。如果不是叶节点，当last比最大（小）的子节点大（小），用last代替，如是非递归调用则要调整，完成；否则，用子节点中最大（小）的值代替，递归删除这个代替值。

　　程序代码：

　　运行结果：

　　练习３：把上例改为小顶堆，然后逐个删除。

　　弹堆（pop）

　　弹出堆顶元素，实际就是删除堆顶元素，然后把这个元素返回。

　　程序代码：

　　运行结果：

　　练习４：把上例改为小顶堆，然后逐个弹出。

　　排序输出

　　就是通过顶堆输出一个有序的数组或列表。把一棵大（小）顶树的顶去掉了，就成了大（小）顶树的森林，因此，顶堆的最值是根节点，次最值是子顶堆根节点的最值者。把没去根的树和去根的两个子树加到下一轮的森林中，循环就可得到排序的列表。

　　程序代码：

　　运行结果：

　　练习５：把上例改为小顶堆，然后输出排序列表。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社