使用Swift实现基于堆的优先级队列
在计算机科学中存在很多问题，其中使用优先级队列作为基础数据结构可以极大地提高算法的时间复杂度。 Dijkstra的最短路径算法就是一个例子，该算法使用优先级队列在图形中搜索两个顶点之间的最短路径。
遗憾的是，Swifts标准库没有默认的优先级队列实现，因此我们将研究如何自行实现基于堆的优先级队列。
要继续使用自己的IDE，请 单击此链接 以获取源代码 ！
什么是优先队列？
优先级队列是一种数据结构，可以对具有相对优先级的对象进行有效的排序。 您可以将一堆对象放入队列，然后根据它们之间相互比较的重要性将它们一一递回。
假设您已经为计算机创建了许多任务，以便它们在将来的某个特定时间运行。 将它们添加到优先级队列将使您的计算机使任务出队，并在仍在等待其截止日期的任务之前获得应执行的对象。
为了实现我们的队列，我们将使用堆结构！
什么是堆？
可以将堆看作一棵树，其中每个节点最多有2个子节点。 堆还具有以下限制：它需要将所有新节点添加到顶层，并尽可能地添加到最左边。 看一下下面的图片：
堆还维护与每个节点的相对大小有关的属性。 最小堆（这是我们将要使用的堆）保持以下属性：每个节点都小于其两个子节点，而最大堆则相反。
为了能够维护此属性，我们将需要进行一些操作以获得正确的节点顺序。 当我们插入一个新节点时，我们将其添加到树顶部左侧的第一个可用位置。 如果完成此操作后min min属性不成立，我们将开始与该节点的父节点交换节点，直到达到再次拥有min堆的状态。 下图显示了将2插入到现有的最小堆中时发生的情况：