Swift数据结构：堆

堆是一个非常整洁的数据结构，可以对最小值或最大值进行优先级排序。 它与树的分层和节点结构有些相似，但是由于它是线性的，因此可以轻松地存储在数组中。

对于视觉人来说，如果我们将其绘制出来，这就是堆的外观：

上图显示了最小（最小）堆，该堆优先排列顶部数据集中的最小值作为根父节点。 在下面，存在值为3和8的节点，它们分别作为父节点的左和右子节点（值为2）存在。

值为3的节点的左子节点为4，右子节点为7。此过程将一直进行下去，直到所有数据集中的值都已布置好为止。 请注意，这些值通常随从顶部到底部的增加而增加。 它们本身不是从左到右组织的，而是按行组织的。

第1行在根节点的位置包含值2。 第2行的左，右子节点的值3和8都大于2。第3行包含了节点3和8的左右子节点。如您所见，两个节点的子节点在值。 希望您开始注意到一种模式。

最小堆中的每个父级可以有0、1或2个子级-所有这些子级的值都大于父级。 最大堆的工作方式完全相反。

堆利用索引系统（如数组）来确定值的顺序及其在堆中的位置（从索引0开始并向上计数）。 如果我们从较早之前引用可视堆图，则索引从上到下，从左到右递增，如下所示：

到目前为止，您所看到的示例都显示了静态数据。 我们没有添加或删除任何项目，但是最重要的是我们可以更改Heap中的数据，否则此数据结构将毫无价值。 在Swift中，我们将首先创建一个名为MinHeap的结构， MinHeap所示：

遵循堆的规则，您可以看到从上到下的每一行通常会逐渐变大，并且每个父节点的子节点都大于其自身。

调用peek()返回您期望的2值，而调用poll()在删除第一项后重新排列堆。 若要查看实际效果，请将以下代码添加到MinHeap结构的底部，然后再次调用dump(myHeap.items) ：

我们做到了！ 现在，我们已经成功地构建了一个最小堆，它对传入的最小值进行优先级排序。删除值后，堆将重新排序，因此下一个最小值位于顶部。 但是在现实世界中可以在哪里使用呢？

在Github Gist上获得完整的源代码：https://gist.github.com/kalub92/d269ba6b2bf05ca7dcbaae64b4ff7a2d

想象一下，您正在为儿科急诊室建立患者摄入系统。 医院希望优先考虑最年轻的患者，以便他们能够尽快接受护理。 想象一下，有几个6、7和8岁的孩子在候诊室，但一个病得很重的1岁孩子进入候诊室并经历了摄入过程。 在时间上，1岁应排在第4位，但该医院希望首先照顾最年轻的患者。 如果在患者摄入计划中使用了Heap，则1岁的孩子会马上去找儿科医生见面。 这是一个特定的用例，但我想知道您的想法。

您认为堆可以在现实世界中有用地实现在哪里。 在下面发表评论，让我们知道！

如果您准备加入我们并了解有关Swift，数据结构和iOS开发的更多信息，请查看Devslopes并注册我们的Apple坡度，以学习构建自己的应用程序和启动基于应用程序的初创公司所需的所有技能。 。