堆

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

堆的常见用途：

• 建立优先级队列。

• 支持堆排序。

• 快速计算集合的最小(或最大)元素。

堆属性

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

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

一个例子：

image.png

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

由于具有此堆属性，因此，max-heap始终将其最大的项存储在树的根目录中。对于最小堆，根始终是树中最小的项。堆属性很有用，因为堆经常被用作优先级队列来快速访问“最重要”元素。

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

堆与常规树相比如何？

堆不能代替二叉搜索树，它们之间有相似之处和不同之处。主要区别如下：

节点顺序。在二叉搜索树(BST)中，左子级必须小于其父级，而右子级必须更大。对于堆来说不是这样。在最大堆中，两个子项都必须小于父项，而在最小堆中，两个子项都必须更大。

记忆。传统的树占用的内存不仅仅是它们存储的数据。您需要为节点对象和指向左/右子节点的指针分配其他存储。堆仅使用普通数组进行存储，并且不使用指针。

平衡。二叉搜索树必须是“平衡的”，以便大多数操作具有O(log n)性能。您可以按随机顺序插入和删除数据，也可以使用AVL树或红黑树之类的东西，但是使用堆，我们实际上不需要对整个树进行排序。我们只希望能够满足heap属性，因此平衡不是问题。由于堆的结构方式，堆可以保证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。左节点和右节点始终彼此相邻存储。

让我们在示例中使用这些公式。填写数组索引，我们应该获得父节点和子节点在数组中的位置：

Node	Array index (i)	Parent index	Left child	Right child
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它不是有效的数组索引。同样，node (2)，(5)和(1)没有子项，因为这些索引大于数组的大小，因此在使用它们之前，我们始终必须确保计算出的索引实际上是有效的。

回想一下，在最大堆中，父级的值始终大于(或等于)其子级的值。这意味着所有数组索引必须满足以下条件i：

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

验证此堆属性对于示例堆中的数组是否成立。

如您所见，这些方程式使我们无需指针即可查找任何节点的父级或子级索引。这不仅只是取消引用指针，还很复杂，但这是一个折衷方案：我们节省了内存空间，但需要额外的计算。幸运的是，计算速度很快，只需要O(1)时间。

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

image.png

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

image.png

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

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

image.png

除非当前最低级别已满，否则您无法启动新级别，因此堆始终具有以下形状：

image.png

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

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

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

这是有效的堆吗？答案是肯定的！从低到高排序的数组是有效的最小堆。我们可以如下绘制该堆：

image.png

堆属性对于每个节点均有效，因为父节点始终小于其子节点。(亲自验证从高到低排序的数组始终是有效的最大堆。)

注意：但是，并非每一个min-heap都一定是一个有序数组！它仅以一种方式起作用。要将堆转换回已排序的数组，需要使用堆排序。

更多数学！

如果您感到好奇，这里还有一些描述堆的某些属性的公式。您不需要内心地了解这些内容，但是有时它们会派上用场。随时跳过此部分！

树的高度定义为从根节点到最低叶节点或更正式地走的步骤数：高度是节点之间的最大边数。高度为h的堆具有h +1个级别。

该堆的高度为3，因此具有4个级别：

image.png

具有n个节点的堆的高度为h = floor(log2(n))。这是因为在添加新级别之前，我们总是会完全填满最低级别。该示例有15个节点，因此高度为floor(log2(15)) = floor(3.91) = 3。

如果最低级别完全满了，则该级别包含2 ^ h个节点。树上方的其余树包含2 ^ h-1个节点。填写示例中的数字：最低级别有8个节点，实际上是2^3 = 8。前三个级别总共包含7个节点，即2^3 - 1 = 8 - 1 = 7。

因此，整个堆中的节点总数n为2 ^(h + 1)-1。在示例中，2^4 - 1 = 16 - 1 = 15。

有至多ceil(n/2^(h+1))高度的节点在一个 n-element heap。

叶子节点始终位于数组索引floor(n / 2)到n-1处。我们将利用这一事实从阵列中快速构建堆。如果您不相信该示例，请对其进行验证。;-)

仅有的一些数学事实可以帮助您改善生活。

你能用堆做什么？

在插入或删除元素之后，有两项基本操作可确保堆是有效的max-heap或min-heap：

• shiftUp()：如果元素大于其父元素(最大堆)或小于其父元素(最小堆)，则需要与父元素交换。这使它向上移动到树上。

• shiftDown()。如果元素比其子元素小(最大堆)或更大(最小堆)，则需要向下移动树。此操作也称为“堆化”。

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

以下是在原始操作上构建的其他操作：

• insert(value)：将新元素添加到堆的末尾，然后用于shiftUp()修复堆。

• remove()：删除并返回最大值(最大堆)或最小值(最小堆)。要通过删除元素来填补剩余的空缺，将最后一个元素移到根位置，然后shiftDown()修复堆。(有时称为“提取最小值”或“提取最大值”。)

• removeAtIndex(index)：就像remove()例外一样，它允许您从堆中删除任何项，而不仅仅是根。shiftDown()如果新元素的子元素不正常，则调用，如果元素shiftUp()的父元素不正常，则调用。

• replace(index, value)：为节点分配较小(最小堆)或较大(最大堆)的值。因为这会使堆属性无效，所以它用于shiftUp()修补事物。(也称为“减少键”和“增加键”。)

上述所有操作都需要时间O(log n)，因为上移或下移的费用很高。还有一些操作需要更多时间：

• search(value)。堆并不是为有效搜索而构建的，但是replace()and 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插入此堆：

image.png

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

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

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

这对应于以下树：

image.png

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

不幸的是，由于(2)位于上面(16)，不再满足heap属性，因此我们希望较高的数字高于较低的数字。(这是一个最大堆。)

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

image.png

我们尚未完成，因为(10)还小于(16)。我们一直将插入的值与其父级交换，直到父级更大或到达树顶为止。这称为上移或筛分，并在每次插入后完成。它使数字太大或太小都会“浮起”树。

最后，我们得到：

image.png

现在，每个父母都比孩子更大。

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

移除根

让我们(10)从这棵树中删除：

image.png

顶部的空白处会发生什么？

image.png

插入时，我们将新值放在数组的末尾。在这里，我们做相反的事情：我们拿走我们拥有的最后一个对象，将其粘贴在树的顶部，然后恢复heap属性。

image.png

让我们看一下如何调低档位 (1)。为了维护此max-heap的heap属性，我们希望获得最大数量的top。我们有两个候选人可以与(7)和交换名额(2)。我们在这三个节点之间选择最高的数字。也就是(7)，因此交换(1)并(7)给我们下面的树。

image.png

继续向下移动，直到该节点没有任何子节点或该节点大于其两个子节点为止。对于我们的堆，我们只需要再进行一次交换即可恢复堆属性：

image.png

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

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

删除任何节点

在绝大多数情况下，您将在堆的根部删除对象，因为这是为堆设计的。

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

让我们再次以示例树为例，并删除(7)：

image.png

提醒一下，该数组是：

[ 10, 7, 2, 5, 1 ]

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

[ 10, 1, 2, 5, 7 ]

最后一个元素是我们将返回的元素；我们将调用removeLast()将其从堆中删除。在(1)现在是乱序，因为它比其子小，(5)但坐在树高。我们致电shiftDown()维修。

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

image.png

现在(5)与交换(8)。由于(8)大于其父项，因此我们需要致电shiftUp()。

从数组创建堆

将数组转换为堆可能很方便。这只是随机排列数组元素，直到满足heap属性为止。

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

  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()，则需要获取该元素的索引。搜索是执行此操作的一种方法，但是速度很慢。

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

让我们再次以示例堆为例：

image.png

如果要搜索node的索引(1)，可以通过[ 10, 7, 2, 5, 1 ]线性搜索逐步遍历数组。

即使没有考虑到堆属性的构想，我们仍然可以利用它。我们知道，在最大堆中，父节点始终大于其子节点，因此，如果父节点已经小于要寻找的值，则可以忽略那些子节点(及其子节点，依此类推...)。

假设我们要查看堆是否包含值8(不包含)。我们从根本开始(10)。这不是我们想要的，所以我们递归地查看它的左子对象和右子对象。左孩子是(7)。这也不是我们想要的，但是由于这是一个最大堆，我们知道查看的子项是没有意义的(7)。它们总是小于7并且因此永远不等于8; 同样，对于合适的孩子，(2)。

尽管有很小的优化，搜索仍然是O(n)操作。

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

原文链接：堆