《我的第一本算法书》阅读笔记 1-7 堆

古城微笑少年丶 2022-10-22 04:17 196阅读 0赞

**目录**

堆介绍

向堆添加数据

从堆取出数据

解说

应用示例

来源

--------------------

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）（树形结构的详细讲解 在 4-2 节）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。

--------------------

### 堆介绍 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

这就是堆的示例。结点内的数字就是存储的数据。堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

在堆中存储数据时必须遵守这样一条规则 ：子结点必定大于父 结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据 时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行， 把数据加在这一行的最左端。

### 向堆添加数据 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

我们试试往堆里添加数 字5。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

首先按照**02**的说明寻找新数据的位置。该图中最下面一排空着一个位置，所以将数据加在此处。

![20210403204959545.png][]

如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置。

![20210403205040511.png][]

这里由于父结点的6大于子结点的5，所以交 换了这两个数字。重复这样的操作直到数据都符合规则，不再需要交换为止。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

现在，父结点的 1 小于子结点的 5，父结点的数字更小，所以不再交换。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

这样，往堆中添加数据的操作就完成了。

--------------------

### 从堆取出数据 ###

![20210403205157701.png][]

从堆中取出数据时，取出的是最上面的数据。 这样，堆中就能始终保持最上面的数据最小。

![20210403210705273.png][]

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

![20210403210747505.png][]

按照01中说明的排列顺序，将最后的数据（此 处为6）移动到最顶端。

![20210403210823426.png][]

如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换。

![20210403210858575.png][]

这里由于父结点的6大于子结点（右）的5大于子 结点（左）的3，所以将左边的子结点与父结点进 行交换。重复这个操作直到数据都符合规则，不 再需要交换为止。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

现在，子结点（右）的 8 大于父结点的 6 大于子 结点（左）的 4，需要将左边的子结点与父结点 进行交换。

![20210403210926442.png][]

这样，从堆中取出数据的操作便完成了。

--------------------

### 解说 ###

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

另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据 的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为 n，根据堆的形状特点可知树的高度为 ![\\log\_2n][log_2n] ，那么重构树的时间复杂度便为 O(logn)。

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

### 应用示例 ###

如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。比如 4-5 节中提到的狄克斯特拉算法，每一步都需要从候补顶点中选择距离起点最近的那个 顶点。此时，在顶点的选择上就可以用到堆。

### 来源 ###

**《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/d00735e78b6f4dfe986ee8693dc6ea0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/f05fea1df89f4fad9b06ce9ca6903cec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/f63d751b7c994939a8aa8d435d1416f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/b5af11a3ea74406587a90b391165e6fe.png
[20210403204959545.png]: /images/20221022/de9f87ef6d6c4ca3af85aab0d7ced766.png
[20210403205040511.png]: /images/20221022/d051c00c380f4a6cbd83cc2d9d519f9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/338eaef83d544391914b702c772a0f4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/9d81d2bdd772445c8956697f5ac08b11.png
[20210403205157701.png]: /images/20221022/7d164287152146b6b509025a86b6468a.png
[20210403210705273.png]: /images/20221022/0fb03f8d819e4aed8895b7e367c39db1.png
[20210403210747505.png]: /images/20221022/4bcadb802fec4e34b278204ae4dc6600.png
[20210403210823426.png]: /images/20221022/75ef6d6ff6ab4b8c8632e596c5fe853a.png
[20210403210858575.png]: /images/20221022/f4e688c97466448d9e6c6d064d8cd72e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/4b344e31dc2546e39740e63ba2591606.png
[20210403210926442.png]: /images/20221022/4f033ba5f3f643b78e1a97c43caed888.png
[log_2n]: https://latex.codecogs.com/gif.latex?%5Clog_2n