算法和数据结构1.7堆

堆是一种树形结构，被用于实现优先队列（pripority queues）.优先队列是一种数据结构，可以自由添加数据。

但是取数据是要从最小值开始按顺序取出。在堆的数据结构中，各个顶点被称为“节点”（node）,数据就存储在这些结点中。

担心时间久远记不住，直接上图好回忆。

1.堆的示例

在下图的例子中，结点按照1，3，6，4，8，7的顺序排列，这就是堆的示例。

1.png

结点内的数字就是存储的数据。

堆中的每个结点最多有两个子结点。

树的形状取决于数据的个数。

另外，结点的排序为从上到下，从左到右。

2.堆的添加数据

规则1：在堆中存储数据时候，必须遵循这样一条规则：子结点必定大于父结点。

因此，最小值被存储在了顶端端的根结点中。

往堆中添加数据时候，为了遵循上面的规则，一般会把新的数据放在最下面一行靠左的位置。
如果最下面一行没有多余的空间，就再往下另起一行，把数据加在这一行的最左端。

下图，尝试添加数据5到堆里面。

2.png

首先找到新添加数据的位置，将5放在堆里面

3.png

其次按照父节点小于子节点的规则，将5和6的父子位置调换

4.png

然后排查5，6，7这三个节点，符合父子节点规则。

最后排查1 ，3，5这这三个节点，符合父子节点规则。

最终的结果是如下图所示的堆结构：

5.png

3.堆的删除数据（取数据）

从堆中取数据时候，取出的是最上面的数据。

这样就保证最上面的数据最小。

6.png

由于最上面的数据被取出，因此堆结构也需重新调整。

首先先将堆中最下面，最右侧的一个节点值移到堆的顶端。

7.png

这里将6的节点放在顶端，然后再根据父亲节点小于子节点的规则，从左到右，从上到下开始调整堆。

8.png

6，3，5的调整结果如下，3和6的父子节点互换。

9.png

接下来按照规则继续调整6，4，8的位置，4和6的父子节点互换。

最后排查5，7，不需要互换。到此堆的取数据和堆的调整完成，结果如下图。

10.png

时间计算

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度为O(1).

另外，因为取出数据之后需要将最后的数据移动到顶端，然后一边比较它与子节点的数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。

这里假设数据量为n,根据堆的形状特性，（完全二叉树）可知树的高度为log₂n,那么重构树的时间复杂度为O(logn)。

添加数据也一样，在堆的后面添加数据后，数据会一边比较和父节点和大小，一边向上移动，直到满足条件为止，所以添加数据所需要的运行时间与树的高度成正比，也是O(logn)。

应用

如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。