堆就是用数组实现的二叉树，所以它的内存占用小于二叉树，并且没有二叉树带有的父指针或者子指针。堆常用于构建优先队列、堆排序、快速找出一个集合中的最小值（或最大值)等操作。尤其堆排序，占用空间小，速度接近二叉排序树。相比于二叉树排序是一种更优的选择。
堆
简单来说，堆就是用一维数组元素之间的位置关系来表达数据结构中元素的二维或更高维的关系。确切地说，就是把一个数据结构按确定的降维算法逻辑放到一个数组里。这个算法逻辑可以是一个树结构，也可以是一个排序结构，甚至可以是自定义的一个任意逻辑。这些逻辑把数组分割成许多个大小不一的数据单元，每个单元按一定规则排列其中的数据。下图举例说明满二叉树转为堆。
堆是一个数组（或链表），但数组中每个数据是按照某种逻辑指定摆放的，上图是把二叉树演变为数组，这个数组就是一个堆。堆和树的区别如下：
(1)内存占用：普通树占用的内存空间比它们存储的数据要多。它必须为节点对象以及左/右子节点指针分配额外的内存，堆仅使用数组，且不使用指针（可以用普通树来模拟堆，但空间浪费比较大，不太建议这么做)。
(2)平衡：二叉搜索树必须在“平衡”的情况下，其大部分操作的复杂度才能达到O(nlog2n)。使用者可以按任意顺序位置插入/删除数据，或者使用平衡(AVL)树。堆是采用数组下标访问的，因此树中的所谓“平衡”在堆中没多大意义。堆的这种访问方式保证O(nlog2n)的性能。
(3)排序和搜索：在二叉树中排序和搜索都很快，但在堆中每次搜索都需要计算一次索引位置，无形中加大了计算量，所以速度要略微慢于二叉树。
二叉堆
二叉堆是个一维数组（或链表），它对应的算法逻辑是已经介绍过的完全二叉树，完全二叉树与二叉堆的映射对应关系的图解如下图所示。
从图可得到如下推论：
(1)顶点6的左子节点下标位置在：2×0+1=1下标(6自身的下标为0)。
(2)顶点6的右子节点下标位置在：2×0十2=2下标。
(3)节点3的左子节点下标位置在：2×1+1=3下标(3自身的下标为1)。
(4)节点3的右子节点下标位置在：2×1+2=4下标。
......
推导出数组中每个节点的左右子节点位置在此节点数组下标n的2n十1和2n+2位置上，归纳为：
当前节点左子节点下标：2×n+1。
当前节点右子节点下标：2×n十2。
n为当前节点在数组中的下标。
二叉堆的插入
因为二叉堆是数组或列表，无须创建节点，直接把数据插入到数组的指定下标即可。关键在于找对合乎算法的下标位置。它的算法逻辑如下：每插入一个新的数据，从根节点开始查找插人位置，如果待插入值小于当前元素值（下标n),向后续2n+1位置继续查找，如果大于当前值，则向后续2n+2位置查找，图解步骤如下图所示。
由于Python语言中list列表初始化为空，需要不断追加进元素才能增加数组下标，所以要用循环把列表长度填充到二叉堆最长下标的位置，因而需要在代码中增加一计数器(end)记录最长下标位置。
程序代码：
运行结果：
中序遍历
堆的遍历也是遵循生成它的算法逻辑，二叉堆的算法逻辑是完全二叉树，所以遍历方式也参照完全二叉树。二叉堆与完全二叉树的对应如下图所示。
二叉堆遍历的算法分析：堆的左子节点算法是2×n+1，右子节点算法是2×n+2，按中序遍历，即先左再中后右的方式遍历，二叉堆中序遍历下图所示。3,4,5放入结果集后再把根节点6放入结果集，然后查找根节点的右指针，如果有右节点，继续按左、中、右的顺序进行中序遍历，直到遍历出整个二叉堆的所有值。
程序代码：
运行结果：
分层遍历
二叉堆是完全二叉树的降维形式，因为完全二叉树次底层和以上都是满配的，因此把二叉堆按倍增的形式1,2,4,8,16,......划层就行。假设是满二叉树，如果层数从0开始，那第n层的前所有层的数量和比第n层的数量（2^n）少1，即2^n-1。这样得到第n层开始节点的下标是2^n-1。同理得到第n层最后一个节点的下标是2^(n+1)-1-1，由于结束不包含，所以结束下标是2^(n+1)-1。完全二叉树的最后一层可能不满，因此要检查结束下标是否已经超过最后节点下标加1。
程序代码：
运行结果：
练习题１：用二叉堆插入数据[6,1,4,3,5,2,11,9,0,10,7,-1,-3]，然后直接打印列表、中序遍历和分层遍历。
学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：
Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。
更多课程请打开“学思营”同步网站：
http://www.5xstar.com/doc.html
参考资料：
１、《Python算法图解》何韬编著 清华大学出版社