二叉堆

二叉堆是一种基于二叉树的特殊存储结构，它可以看成是一棵完全二叉树。常见的有最大堆又叫大顶堆、大根堆和最小堆又叫小顶堆、小根堆。在最大堆中的任何一个子树中都有父节点的值都大于子节点的值。在最小堆中的任何一个子树中父节点的值都小于子节点。

虽然二叉堆是基于二叉树的，但是实际中，我们经常使用数组来存储二叉堆，实现逻辑上的树形结构，其具备以下特点：

• 数组中每一个元素代表二叉堆中的一个节点。
• 父节点和子节点在数组中的存储位置存在特殊的关系，第i个节点，其左右子节点的存储位置分别是2i+1和2i+2，其父节点的存储位置是floor((i-1)/2)。

比如说使用数组存储的最大堆[100, 19, 36, 17, 3, 25, 1, 2, 7]，它树形结构如下。

通过上面可以看出，节点17的在数组中的存储位置是3，它的左右子节点存储位置分别是2*3+1=7和2*3+2=8，它的父节点的存储位置是floor((3-1)/2)=1。这个特性在后续操作、维护堆的时候非常有用。

堆的应用

• 堆排序，利用堆数据结构实现的一种排序算法。
• 优先队列，很多优先队列的实现都是基于堆。
• 在图算法中的应用，比如最小生成树Prim算法，还有最短路径Dijkstra算法。

二叉堆最主要的两种操作，插入和删除，因为操作完成之后仍然要维持堆的特性，所以需要对堆中的部分节点进行调整，这两种操作的时间复杂度都是O(logN)，下面以最大堆为例，看看堆的插入和删除操作。

插入逻辑

1. 插入时先将数据插入在二叉堆最后面，也就是数组的尾部。
2. 然后将当前节点跟它的父节点进行比较。
   *) 如果当前节点大于父节点，则将父节点与当前节点交换。
   *) 如果小于等于父节点，则停止操作。
3. 重复第2步操作，直到当前节点小于等于父节点。

删除逻辑

1. 首先用二叉堆最后面的节点替换最顶部的节点，即数组的最后一个元素替换第一个元素。
2. 然后将当前节点和它的左右子节点一起对比。
   *) 如果左子节点最大，则将当前节点与左子节点交换。
   *) 如果右子节点最大，则将当前节点与右子节点交换。
   *) 如果当前节点最大，则停止操作。
3. 重复第2步操作，直到当前节点大于等于其左右子节点。

下面看看数组[1,3,2,5,6,4]依次插入到最大堆和从最大堆删除的动画演示。