第22章：堆

堆是另一种经典的基于树的数据结构，具有特殊的属性，使其非常适合于快速获取最大或最小的元素。

在这一章中，你将专注于创建和操作堆。你将看到获取一个集合的最小和最大元素是多么方便。

什么是堆？

堆是一个完整的二进制树，也被称为二进制堆，可以用数组来构建。

注意：不要将这些堆与内存堆混淆。在计算机科学中，堆这个术语有时被混淆地用来指代内存池。内存堆是一个不同的概念，不是你在这里要学习的内容。

堆有两种类型。

  1. 最大堆，其中数值较高的元素有较高的优先级。

  2. 最小堆，其中数值较低的元素有较高的优先级。

堆的属性

一个堆有一个必须始终满足的基本特性。这个特性被称为堆不变性或堆属性。

在一个最大堆中，父节点必须总是包含一个大于或等于其子节点中的值的值。根节点将始终包含最高值。

在min heap中，父节点必须总是包含一个小于或等于其子节点中的值的值。根节点将总是包含最低的值。

堆的另一个基本属性是它是一个几乎完整的二叉树。这意味着每一层都必须被填满，除了最后一层。这就像一个视频游戏，在完成当前级别之前，你不能进入下一个级别。

堆的应用

堆的一些实际应用包括。

注意：你将在第24章学习优先级队列，在第32章学习堆排序，在第42和44章分别学习Dijkstra和Prim的算法。

常见的堆操作

打开本章的空启动器playground。从定义下面的基本堆类型开始。

这个类型包含一个数组，用来保存堆中的元素，以及一个排序函数，定义了堆应该如何排序。通过在初始化器中传递一个适当的函数，这个类型可以创建最小和最大堆。

你如何表示一个堆呢？

树持有存储对其子代的引用的节点。在二叉树的情况下，这些是对左边和右边孩子的引用。堆确实是二叉树，但是它们可以用一个简单的数组来表示。这种表示方法可能看起来是建立树的一种不寻常的方式。但是这种堆的实现方式的好处之一是高效的时间和空间复杂性，因为堆中的元素都是一起存储在内存中。以后你会看到，交换元素将在堆的操作中发挥很大的作用。这种操作在数组中也比在二叉树数据结构中更容易做到。看看你如何使用数组来表示一个堆。以下面这个二进制堆为例。

为了把上面的堆表示成一个数组，你从左到右逐级迭代每个元素。

你的遍历看起来像这样。

当你往上走的时候，你会有比之前那一层多一倍的节点。

现在很容易访问堆中的任何节点。你可以把这比作你如何访问数组中的元素。你可以使用简单的公式来访问数组中的节点，而不是沿着左边或右边的分支进行遍历。

给定一个节点的零基索引i。

你可能想获得一个节点的父节点。在这种情况下，你可以解决i的问题。给定一个索引为i的子节点，这个子节点的父节点可以在索引floor( (i 1) / 2)找到。

注意：在实际的二叉树上向下遍历以获得一个节点的左和右的子节点是一个O(log n)操作。同样的操作在一个随机访问的数据结构中只是O(1)，比如一个数组。

接下来，利用你的新知识为Heap添加一些属性和便利方法。

现在你已经很好地理解了如何用数组来表示一个堆，你将看看一个堆的一些重要操作。

#从堆中删除

一个基本的移除操作是将根节点从堆中移除。

以下面这个最大的堆为例。

删除操作将删除根节点的最大值。要做到这一点，你必须首先将根节点与堆中的最后一个元素交换。

一旦你交换了这两个元素，你就可以删除最后一个元素，并存储它的值，以便你以后可以返回它。

现在，你必须检查最大堆的完整性。但首先要问自己，"它还是一个最大堆吗？"

请记住。最大堆的规则是，每个父节点的值必须大于或等于其子节点的值。由于堆不再遵循这一规则，你必须进行筛分。

为了执行向下筛选，你从当前值3开始，并检查它的左边和右边的子节点。如果其中一个子代的值大于当前值，你就把它和父代交换。如果两个子代都有更大的值，你就把父代和有更大值的子代交换。

现在，你必须继续向下筛选，直到该节点的值不大于其子节点的值。

一旦你到达终点，你就完成了，而且最大堆的属性也被恢复了

删除的实现

给Heap添加以下方法。

下面是这个方法的工作原理。

  1. 检查堆是否为空。如果是，则返回nil。

  2. 将根与堆中的最后一个元素交换。

  3. 删除最后一个元素（最大值或最小值）并返回。

  4. 该堆可能不再是最大或最小堆，所以你必须进行筛下，以确保它符合规则。

现在，为了了解如何对节点进行筛选，在remove()之后添加以下方法。


siftDown(from:) 接受一个任意的索引。该索引中的节点将始终被视为父节点。下面是该方法的工作原理。

  1. 存储父节点的索引。

  2. 继续筛查，直到返回。

  3. 获取父代的左和右的子代索引。

  4. 候选变量用于跟踪与父代交换的索引。

  5. 如果有一个左边的孩子，而且它的优先级比它的父辈高，就把它作为候选者。

  6. 如果有一个右边的孩子，而且它的优先级更高，它将成为候选者。

  7. 如果候选者仍然是父代，你已经达到了终点，不需要再进行筛选。

  8. 将候选者与父本交换，并将其设置为新的父本，继续进行筛选。

复杂度。remove()的总体复杂度是O(log n)。交换数组中的元素只需要O(1)，而在堆中筛选元素需要O(log n)的时间。

现在你如何向堆中添加？

插入到堆中

假设你在下面的堆里插入一个7的值。

首先，你把这个值加到堆的末端。

现在，你必须检查max heap的属性。你现在必须向上筛选，而不是向下筛选，因为你刚刚插入的节点可能比它的父节点有更高的优先级。这种向上筛选的工作方式很像向下筛选，即比较当前节点和它的父节点，并在需要时将它们交换。



现在你的堆已经满足了最大堆的属性

插入的实现

在Heap中添加以下方法。

正如你所看到的，这个实现是非常直接的。

复杂度。insert(_:)的总体复杂度是O(log n)。在数组中追加一个元素只需要O(1)，而在堆中筛选元素需要O(log n)。

这就是在堆中插入一个元素的全部内容。

到目前为止，你已经看了从堆中移除根元素和插入堆中的情况。但如果你想从堆中删除任何任意元素呢？

从一个任意的索引中删除

在Heap中添加以下内容。


要从堆中删除任何元素，你需要一个索引。让我们来看看这是如何进行的。

  1. 检查索引是否在数组的范围内。如果不是，返回nil。

  2. 如果你要删除堆中的最后一个元素，你不需要做任何特别的事情。只需删除并返回该元素。

  3. 如果你不删除最后一个元素，首先将该元素与最后一个元素交换。

  4. 然后，返回并删除最后一个元素。

  5. 最后，进行下筛和上筛来调整堆。

但是--为什么你要同时进行下筛和上筛？

假设你想删除5。你将5与最后一个元素交换，也就是8。你现在需要执行一个上筛，以满足最大堆属性。

现在，假设你想删除7。你用最后一个元素1交换了7，现在你需要执行一个下移的操作来满足最大堆的属性。

下移案例 从堆中移除一个任意的元素是一个O(log n)操作。但是你如何找到你想删除的元素的索引呢？

在堆中搜索一个元素

为了找到你想删除的元素的索引，你必须在堆中进行搜索。不幸的是，堆并不是为快速搜索而设计的。使用二进制搜索树，你可以在O(log n)时间内进行搜索，但是由于堆是使用数组建立的，而数组中的节点排序是不同的，你甚至不能进行二进制搜索。

复杂度。在堆中搜索一个元素，在最坏的情况下，是一个O(n)操作，因为你可能要检查数组中的每一个元素。


让我们来看看这个执行情况。

  1. 如果索引大于或等于数组中的元素数，则搜索失败。返回nil。

  2. 检查你要找的元素是否比当前索引i处的元素有更高的优先级，如果有，你要找的元素就不可能在堆中更低。

  3. 如果该元素与索引i处的元素相等，则返回i。

  4. 从i的左边的子元素开始，递归地搜索该元素。

  5. 递归搜索从i的右边的孩子开始的元素。

  6. 如果两个搜索都失败了，则搜索失败。返回nil。

注意：虽然搜索需要O(n)时间，但你已经通过利用堆的属性和搜索时检查元素的优先级来努力优化搜索。

建立一个堆

你现在已经拥有了表示一个堆的所有必要工具。为了总结本章，你将从一个现有的元素数组中建立一个堆，并对它进行测试。更新Heap的初始化器，如下。

初始化器现在需要一个额外的参数。如果提供了一个非空的数组，你就用它作为堆的元素。为了满足堆的属性，你从第一个非叶子节点开始向后循环数组，并向下筛选所有的父节点。你只循环了一半的元素，因为筛选叶节点没有意义，只有父节点。

测试

是时候试试了。在你的playground上添加以下内容。

这个循环创建了一个最大的堆，因为>被用作排序谓词，并逐一移除元素，直到它为空。注意，元素从大到小被移除，以下数字被打印到控制台。

关键点

堆操作的时间复杂度

上一章 目录 下一章