【译】Swift算法俱乐部-堆

作者: Andy_Ron | 来源:发表于2019-01-11 11:02 被阅读70次

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。

本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Heap

堆(Heap)

这个话题已经有个辅导文章

堆是数组内的二叉树，因此它不使用父/子指针。堆基于“堆属性”进行排序，“堆属性”确定树中节点的顺序。

堆的一般用途：

构建优先队列。
支持堆排序。
快速计算集合中最大（或最小）值。
给你的非程序员朋友留下深刻影响。

堆属性

有两种堆：max-heap 和 min-heap，它们存储树节点的顺序不同。

在max-heap中，每个父节点的值大于其子节点。在min-heap中，每个父节点的值都小于其子节点。这称为“堆属性”，对于树中的每个节点都是如此。

一个例子：

A max-heap

这是一个max-heap，因为每个父节点都大于其子节点。 (10)大于(7)和(2)。 (7)大于(5)和(1)。

堆属性的结果是，max-heap始终将其最大项存储在树的根节点中。对于min-heap，根节点始终是树中的最小项。堆属性很有用，因为堆通常用作优先队列来快速访问“最重要的”（译注：最大或最小）元素。

注意： 堆的根节点是最大或最小元素，但其他元素的排序顺序是不可预测的。例如，最大元素始终位于max-heap中的索引0处，但最小元素不一定是最后一个元素。 —— 唯一的保证是，最小元素是叶节点之一，但不知道是哪一个。

堆与常规树对比

堆不是二叉搜索树的替代品，它们之间存在相似之处和不同之处。以下是一些主要差异：

节点的顺序。在二叉搜索树（BST）中，左子节点必须小于其父节点，右子节点必须更大。堆不是这样。在max-heap中，两个子节点必须小于父节点，而在min-heap中，子节点必须大于父节点。

内存。传统的树比它们存储的数据占用更多的内存。需要为节点对象和指向左/右子节点的指针分配额外的存储空间。堆只使用普通数组进行存储，不使用指针。

平衡。 二叉搜索树（BST）必须“平衡”，以便大多数操作具有O(log n)性能。您可以按随机顺序插入和删除数据，也可以使用AVL树或红黑树，但我们实际上并不需要对整个树进行排序。我们只是希望实现堆属性，因此平衡不是问题。由于堆的结构方式，堆可以保证 O(log n) 的性能。

搜索。 虽然在二叉树中搜索速度很快，但在堆中搜索速度很慢。搜索不是堆中的最高优先级，因为堆的目的是将最大（或最小）节点放在前面并允许相对快速的插入和删除。

数组中的树

用数组实现树状结构似乎比较奇怪，但它在时间和空间上都很高效的。

上面例子中的树用数组存储为：

[ 10, 7, 2, 5, 1 ]

这里的所有了！我们不需要比这个简单数组更多的存储空间了。

那么，如果不允许使用任何指针，我们如何知道哪些节点是父节点，哪些节点是子节点？好问题！树节点的数组索引与其父节点和子节点的数组索引之间存在明确定义的关系。

如果i是节点的索引，则以下公式给出其父节点和子节点的数组索引：

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

注意right(i)只是left(i)+ 1。左侧和右侧子节点始终紧挨着存储。

对上面的例子使用这些公式。填写数组索引，我们应该得到数组中父节点和子节点的位置：

节点	数组中的索引(`i`)	父节点索引	左子节点索引	右子节点索引
10	0	-1	1	2
7	1	0	3	4
2	2	0	5	6
5	3	1	7	8
1	4	1	9	10

验证这些数组索引确实对应于上面树的图片。

注意： 根节点(10)没有父节点，因为-1不是有效的数组索引。同样，节点(2)，(5)和(1)没有子节点，因为那些索引大于数组大小，所以用它们之前我们总是要确保我们计算的索引实际上是有效的。

回想一下，在max-heap中，父节点的值总是大于（或等于）其子节点的值。这意味着对于所有数组索引i必须满足以下条件：

array[parent(i)] >= array[I]

验证此堆属性是否适用于示例堆中的数组。

如您所见，这些等式允许我们在不需要指针的情况下找到任何节点的父索引或子索引。这样消除了使用指针的复杂，这是一种权衡：我们节省了内存空间，但需要额外的计算。幸运的是，计算速度很快，只需要 O(1) 时间。

理解树中数组索引和位置之间的这种关系很重要。下面👇是一个更大的堆，有15个节点分为四个级别：

Large Heap

此图片中的数字不是节点的值，而是存储节点的数组索引！下面👇是数组索引对应树的不同级别：

The heap array

要使公式起作用，父节点必须出现在数组中的子节点之前。你可以在上面的图片中看到。

请注意，此方案有局限性。您可以使用常规二叉树执行以下操作，但不能使用堆执行以下操作：

Impossible with a heap

除非当前最低级别已满，否则无法开启新级别，因此堆总是具有这种形状：

注意： 您可以使用堆模拟常规二叉树，但这会浪费空间，您需要将一些数组索引标记为空。

突击测验！假设我们有数组：

[ 10, 14, 25, 33, 81, 82, 99 ]

这是一个有效的堆吗？答案是肯定的！从低到高的排序数组是有效的min-heap。我们可以按如下方式绘制这个堆：

堆属性适用于每个节点，因为父节点始终小于其子节点。（自己验证从高到低排序的数组始终是有效的max-heap。）

注意：但并非每个min-heap都必须是一个排序数组！排序数组只是一种特殊情况。要将堆重新转换为已排序的数组，需要使用堆排序。

你能用堆做什么？

在插入或删除元素之后，有两个必要的原始操作来确保堆是有效的max-heap或min-heap：

shiftUp()：如果元素比其父元素更大（max-heap）或更小（min-heap），则需要与父元素交换，这使元素向上移动。
shiftDown()。如果元素比子元素小（max-heap）或更大（min-heap），这个操作使元素向下移动，也称为“堆化(heapify)”。

向上或向下移动是一个递归过程，需要O(log n)时间。

以下是基于原始操作的其他操作：

insert(value)：将新元素添加到堆的末尾，然后使用shiftUp()来修复堆。
remove()：删除并返回最大值(max-heap）或最小值(min-heap）。为了填充元素删除后留下的位置，让最后一个元素移动到根位置，然后使用shiftDown()修复堆。 (有时称为“提取最小值”或“提取最大值”。）
removeAtIndex(index)：类似remove()，不仅可以删除根节点，也可以从堆中删除任何节点。如果新元素与其子元素不规整，则调用shiftDown();如果元素与其父元素不规整，则调用shiftUp()。
replace(index, value)：为节点分配一个较小(min-heap）或较大(max-heap）的值。因为这会使堆属性失效，所以它使用shiftUp()来修复。 (也称为“减少键”和“增加键”。）

以上所有操作都需要时间O(log n)因为向上或向下移动是昂贵的。还有一些操作需要更多时间：

search(value)。堆不是为高效搜索而构建的，但replace()和removeAtIndex()操作需要节点的数组索引，因此您需要找到该索引。时间：O(n)。
buildHeap(array)：通过重复调用insert()将数组(未排序的）转换为堆。如果您对此很聪明，可以在O(n)时间内完成。
堆排序。由于堆是一个数组，我们可以使用它的唯一属性将数组从低到高排序。时间：O(n lg n)。

堆还有一个peek()函数，它返回最大(max-heap）或最小(min-heap）元素，而不从堆中删除它。时间：O(1)。

注意： 到目前为止，您将使用堆执行的最常见操作是使用insert()插入新值，并使用remove()删除最大值或最小值。两者都需要O(log n)时间。其他操作用来支持更高级的使用，例如构建优先队列，其中项目的“重要性”在添加到队列后可以改变。

向堆中插入元素

我们来看一个插入示例，详细了解其工作原理。我们将值16插入此堆：

这个堆的数组是[10, 7, 2, 5, 1]。

插入新项目的第一步是将其附加到数组的末尾。该数组变为：

[ 10, 7, 2, 5, 1, 16 ]

树结构如下：

(16)被添加到最后一行的第一个可用空间。

不幸的是，堆属性不再满足，因为(2)高于(16)，我们希望更高的数字高于低的数字。 (这是max-heap。)

要恢复堆属性，我们交换(16)和(2)。

我们还没有完成，因为(10)也小于(16)。我们继续将其插入值与其父项交换，直到父项更大或到达树的顶部。这称为shift-up 或 sifting ，并在每次插入后完成。它会使一个太大或太小的数字“浮起”树。

最后，我们得到：

现在每个父节点都比其子节点更大了。

上移所需的时间与树的高度成正比，需要O(log n)时间。（将节点附加到数组末尾所需的时间仅为O(1)，因此不会降低它的速度。）

删除根节点

从树中移除(10)：

顶部的空白怎么办？

插入时，我们将新值放在数组的末尾。在这里，我们做相反的事情：我们采用我们拥有的最后一个对象，将其直接移动到树的顶部，然后恢复堆属性。

让我们来看看如何shift-down(1)。要维护此max-heap的堆属性，我们希望顶部为最大数。我们有两个交换位置的候选者：(7)和(2)。选择这三个节点之间的最高数字位于顶部，那是(7)，所以交换(1)和(7)，得到下面👇的树：

继续向下移动，直到节点没有任何子节点，或者它比两个子节点都大。对于这个堆，只需要一个交换来恢复堆属性：

完全向下移动所需的时间与树的高度成正比，这需要O(log n)时间。

注意： shiftUp()和shiftDown()一次只能修复一个异常元素。如果错误的位置有多个元素，则需要为每个元素调用一次这些函数。

删除任意节点

绝大多数情况下，将删除的是堆根节点，因为这是堆设计的目的。

但是，删除任意元素可能很有用。这是remove()的一般版本，可能涉及shiftDown()或shiftUp()。

让我们再次采用前面的示例树，删除(7)：

提醒一下，数组是：

[ 10, 7, 2, 5, 1 ]

如您所知，删除元素可能会使max-heap或min-heap属性失效。要解决这个问题，我们将要移除的节点与最后一个元素交换：

[ 10, 1, 2, 5, 7 ]

最后一个元素是我们将返回的元素; 我们将调用removeLast()将其从堆中删除。 (1)现在是乱序的，因为它小于它的子节点，(5)是在树中应该更高。我们调用shiftDown()来修复它。

但是，向下移动并不是我们需要处理的唯一情况。也可能发生新元素必须向上移动。考虑如果从以下堆中删除(5)会发生什么：

译注：这个的树对应的数组是[10, 7, 9, 5, 1, 2, 8]。

现在(5)与(8)交换。因为(8)比它的父节点((7))大，我们需要调用shiftUp()。

用数组创建堆

将数组转换为堆可以很方便。只是对数组元素进行洗牌，直到满足堆属性。

在代码中它看起来像这样：

  private mutating func buildHeap(fromArray array: [T]) {
    for value in array {
      insert(value)
    }
  }

我们只要为数组中的每个值调用insert()。简单但不是很高效。这总共需要O(n log n)时间，因为有n个元素，每个插入需要log n时间。

如果你没有跳过前面数学部分，你已经看到，对于任何堆，数组索引n / 2到n-1的元素都是树的叶节点。我们可以简单地跳过那些叶子。我们只需要处理其他节点，因为它们是有一个或多个子节点的父节点，因此可能是错误的顺序。

代码:

  private mutating func buildHeap(fromArray array: [T]) {
    elements = array
    for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
      shiftDown(index: i, heapSize: elements.count)
    }
  }

这里，elements是堆自己的数组。我们从第一个非叶节点开始向后遍历这个数组，并调用shiftDown()。这个简单的循环以正确的顺序放置这些节点以及我们跳过的叶节点。这被称为Floyd算法，只需要O(n)时间。 ✌️

搜索堆

堆不能用于快速搜索，但如果要使用removeAtIndex()删除任意元素或使用replace()更改元素的值，则需要获取该元素的索引。搜索堆速度很慢。

在二叉搜索树中，根据节点的顺序，可以保证快速搜索。由于堆以不同方式对其节点进行排序，因此二叉搜索不起作用，您需要检查树中的每个节点。

再给出上面堆示例：

如果我们想要搜索节点(1)的索引，我们可以通过线性搜索分步搜索数组[10, 7, 2, 5, 1]。

即使堆属性没有考虑到搜索，我们仍然可以利用它。我们知道在max-heap中父节点总是比它的子节点大，所以如果父节点已经小于我们要查找的值，我们可以忽略那些子节点(及其子节点等等）。

假设我们想要查看堆是否包含值8(没有包含)。我们从根(10)开始。这不是我们想要的，所以我们递归地看看它的左右子节点。左边的孩子是(7)。这也不是我们想要的，但由于这是一个max-heap，我们知道查看(7)的子节点是没有意义的，它们总是小于7，因此左侧不会找到8。同样，对于右节点，(2)，也找不到。

尽管有一点优化，搜索仍然是O(n)操作。

注意： 有一种方法可以通过保留一个将节点值映射到索引的附加字典来将查找转换为O(1)操作。如果你经常需要调用replace()来改变构建在堆上的优先队列中对象的“优先级”，这可能是值得做的。

代码

有关用Swift代码实现，请参见Heap.swift。大多数代码都很简单。唯一棘手的是shiftUp()和shiftDown()。

您已经知道有两种类型的堆：max-heap和min-heap。它们之间的唯一区别在于它们如何对节点进行排序：首先是最大值或最小值。

不是创建两个不同的版本，MaxHeap和MinHeap，而只有一个Heap对象，它需要一个isOrderedBefore闭包。此闭包包含确定两个值的顺序的逻辑。你之前可能已经看过了，因为它也是Swift的sort()的工作原理。

要创建一个max-heap整数堆：

var maxHeap = Heap<Int>(sort: >)

要创建一个min-heap整数堆：

var minHeap = Heap<Int>(sort: <)

I just wanted to point this out, because where most heap implementations use the < and > operators to compare values, this one uses the isOrderedBefore() closure.
我只想指出这一点，因为大多数堆实现使用<和>运算符来比较值，这个使用isOrderedBefore()闭包。

扩展阅读

Heap的维基百科

作者：Kevin Randrup， Matthijs Hollemans
翻译：Andy Ron
校对：Andy Ron

【译】Swift算法俱乐部-堆

堆属性

堆与常规树对比

数组中的树

更多数学！

你能用堆做什么？

向堆中插入元素

删除根节点

删除任意节点

用数组创建堆

搜索堆

代码

扩展阅读

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

swift