堆数据结构实现— Swift 4
动机
这篇文章旨在帮助您了解堆数据结构并在Swift中实现它。 在进入实现部分之前，必须先具备swift和heap知识。
什么是堆
堆是一种完整的二叉树的特殊类型，它的父节点与其子节点进行比较，从而为您提供数据结构中的最大值或最小值。
通常有两种类型。
- 最大堆：在最大堆中，父节点将始终大于其子节点。 所有其他节点可以按任何顺序排列
- 最小堆：在最小堆中，父节点将始终小于其子节点。 所有其他节点可以按任何顺序排列
。
注意： 当您只关心最小值或最大值时，堆数据结构很有用。 所有其他值将是无序且无排序的。
优先级队列是可以使用堆数据结构的典型示例。
实作
现在，我们将实现具有所有功能的最小堆。 实现需要执行以下步骤：
1.向堆添加值
2.从堆中删除最少的元素
3.从堆中获取最少的元素
我们开工吧。
创建堆类
堆可以用数组表示。 一个父节点可以有一个左子节点和一个右子节点。 我们可以通过以下方式获取正确的Child的索引和离开的孩子的索引
左儿童索引= 2 *父索引+1
右子索引= 2 *父索引+2
用同样的方式
ParentIndex =（childIndex-1）/ 2
在堆类中实现所需的方法
将这些方法添加到堆类中。
现在，我们将添加在Heap上执行自定义操作的方法。
添加这些方法
peek（）返回堆中的最小元素
poll（）与peek一样，但是它也删除了最小元素
add（）将元素添加到堆中
removeMin（）删除堆中的最小元素
现在您一定在想，什么是heapifyDown（）和heapifyUp（）
让我们实现它们
堆砌
这是在将元素添加到列表之后发生的过程。 因此，如果要在堆中添加元素，只需将其添加到最后一个元素，然后开始与父元素进行比较，直到堆满足条件为止
HeapifyDown
当您删除列表中的最小元素并且堆必须重新排列自身以满足条件时，就会发生此过程。 对于父节点，它将检查子节点是否小于父节点（如果是），然后交换该值。 它一直持续到堆满足其先决条件为止。
让我们添加printMethod来打印堆
让我们使用这些方法来处理堆。
如您所见，我们以随机方式在堆中添加了元素。 但是，在任何时候打印堆时，它总是先打印最小值。
查看移除时的运作方式
这就是您可以对堆执行的所有基本操作。 您可以在堆的帮助下实现优先级队列。 我鼓励您实施它，因为它很有趣。
结论
就是这个帖子。 我们已经了解了Swift中堆实现的基础知识。 您可以使用它做更多的事情，例如优先级队列。