22.堆

堆是另一种经典的基于树的数据结构，具有特殊的属性，使其能够快速获取最大或最小的元素。

在这一章中，你将专注于创建和操作堆。你将看到获取一个集合的最小和最大元素是多么方便。

什么是堆?

堆是一个complete二进制树，也被称为二进制堆，可以使用数组来构建。

Note

不要将这些堆与内存堆混淆。在计算机科学中，堆这个词有时被混淆地用来指代内存池。内存堆是一个不同的概念，不是你在这里要研究的内容。

堆有两种味道：

1. Max堆，其中具有higher值的元素具有较高的优先权。
2. Min堆，其中具有lower值的元素具有较高的优先级。

堆的属性

一个堆有一个必须始终满足的基本特性。这个特性被称为heap invariant或heap property。

在一个max heap中，父节点必须总是包含一个大于或等于其子节点中的值。根节点将总是包含最高的值。

在min heap中，父节点必须总是包含一个小于或等于其子节点的值。根节点将总是包含最低的值。

堆的另一个基本属性是它是一个几乎complete的二叉树。这意味着每一层都必须被填满，除了最后一层。这就像一个视频游戏，在完成当前层级之前，你不能进入下一层。

堆的应用

堆的一些实际应用包括：

• 计算一个集合的最小或最大元素。
• 堆积排序。
• 构建一个优先级队列。
• 构建图算法，如Prim的或Dijkstra的，有一个优先级队列。

Note

你将在第24章学习优先级队列，在第32章学习堆排序，在第42章和44章分别学习Dijkstra算法和Prim算法。

常见的堆操作

打开本章的空启动器操场。首先定义以下基本的Heap类型：

struct Heap<Element: Equatable> {

  var elements: [Element] = []
  let sort: (Element, Element) -> Bool

  init(sort: @escaping (Element, Element) -> Bool) {
    self.sort = sort
  }
}

这个类型包含一个数组来保存堆中的元素，以及一个排序函数来定义堆应该如何排序。通过在初始化器中传递一个适当的函数，这种类型可以同时创建最小和最大堆。

如何表示一个堆？

树持有的节点存储对其子节点的引用。在二叉树的情况下，这些是对左边和右边孩子的引用。堆的确是二叉树，但是它们可以用一个简单的数组来表示。这种表示方法可能看起来是构建树的一种不寻常的方式。但是这种堆的实现方式的好处之一是高效的时间和空间复杂性，因为堆中的元素都是一起存储在内存中的。稍后你会看到，swapping元素将在堆操作中扮演重要角色。这种操作在数组中也比在二叉树数据结构中更容易做到。看看你如何使用数组来表示一个堆。以下面这个二进制堆为例：

为了把上面的堆表示成一个数组，你从左到右逐级遍历每个元素。

你的遍历看起来像这样：

当你上升到一个级别时，你将拥有比之前级别多一倍的节点。

现在很容易访问堆中的任何节点。你可以把这比作你如何访问数组中的元素。你可以使用简单的公式来访问数组中的节点，而不是沿着左边或右边的分支进行遍历。

给定一个节点的零基索引i。

• 这个节点的left child在索引2i + 1处。
• 该节点的right child在索引2i + 2处。

你可能想获得一个节点的父节点。在这种情况下，你可以求解i。给出一个索引为i的子节点，这个子节点的父节点可以在索引floor( (i - 1) / 2)处找到。

Note

遍历一棵实际的二叉树以获得一个节点的左和右的孩子是一个O(log n)的操作。同样的操作在一个随机访问的数据结构中只是O(1)，比如说数组。

接下来，利用你的新知识为Heap添加一些属性和便利方法：

var isEmpty: Bool {
  elements.isEmpty
}

var count: Int {
  elements.count
}

func peek() -> Element? {
  elements.first
}

func leftChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
  (2 * index) + 2
}

func parentIndex(ofChildAt index: Int) -> Int {
  (index - 1) / 2
}

现在你已经很好地理解了如何用数组来表示一个堆，你将看看堆的一些重要操作。

从堆中删除

一个基本的移除操作是将根节点从堆中移除。

以下面这个最大的堆为例：

删除操作将删除根节点的最大值。要做到这一点，你必须首先将root节点与堆中的last元素交换。

一旦你交换了这两个元素，你就可以删除最后一个元素并存储其值，这样你以后就可以返回它。

现在，你必须检查最大堆的完整性。但首先要问自己，"它还是一个最大堆吗？"

请记住。最大堆的规则是，每个父节点的值必须大于或等于其子节点的值。由于该堆不再遵循这一规则，你必须执行sift down。

要进行向下筛分，你从当前值3开始，检查它的左和右子。如果其中一个子代的值大于当前值，你就把它和父代交换。如果两个子代都有更大的值，你就把父代和有更大值的子代交换。

现在，你必须继续向下筛选，直到该节点的值不大于其子节点的值。

一旦你到达终点，你就完成了，最大堆的属性已经恢复了!

删除的实现

给Heap添加以下方法：

mutating func remove() -> Element? {
  guard !isEmpty else { // 1
    return nil
  }
  elements.swapAt(0, count - 1) // 2
  defer {
    siftDown(from: 0) // 4
  }
  return elements.removeLast() // 3
}

以下是这种方法的工作原理：

1. 检查堆是否为空。如果是，则返回nil。
2. 将根与堆中的最后一个元素交换。
3. 删除最后一个元素（最大值或最小值）并返回。
4. 该堆可能不再是最大或最小的堆，所以你必须进行筛下，以确保它符合规则。

现在，为了了解如何对节点进行筛分，在remove()之后添加以下方法：

mutating func siftDown(from index: Int) {
  var parent = index // 1
  while true { // 2
    let left = leftChildIndex(ofParentAt: parent) // 3
    let right = rightChildIndex(ofParentAt: parent)
    var candidate = parent // 4
    if left < count && sort(elements[left], elements[candidate]) {
      candidate = left // 5
    }
    if right < count && sort(elements[right], elements[candidate]) {
      candidate = right // 6
    }
    if candidate == parent {
      return // 7
    }
    elements.swapAt(parent, candidate) // 8
    parent = candidate
  }
}

siftDown(from:)接受一个任意的索引。该索引中的节点将始终被视为父节点。下面是该方法的工作原理：

1. 存储parent的索引。
2. 继续筛选，直到return。
3. 获取父代的左和右的子代索引。
4. candidate变量用于跟踪哪个索引要与父索引交换。
5. 如果有一个左边的孩子，并且它的优先级比它的父辈高，就把它作为候选人。
6. 如果有一个右边的孩子，而且它的优先级更高，它将成为候选者。
7. 如果candidate仍然是parent，你已经到达终点，不需要再进行筛选。
8. 将candidate与parent互换，并将其设置为新的父辈，继续进行筛选。

Complexity

remove()的总体复杂性是O(log n)。交换数组中的元素只需要O(1)，而在堆中筛选元素需要O(log n)的时间。

现在，你如何添加到一个堆中？

插入到堆中

假设你在下面的堆里插入一个7的值：

首先，你把这个值加到堆的末端：

现在，你必须检查max heap的属性。现在你必须sift up，而不是sift down，因为你刚刚插入的节点可能比它的父节点有更高的优先级。这种向上筛选的工作方式与向下筛选很相似，即比较当前节点和它的父节点，如果需要的话，将它们交换。

你的堆现在已经满足了最大堆属性!

插入的实现

给Heap添加以下方法：

mutating func insert(_ element: Element) {
  elements.append(element)
  siftUp(from: elements.count - 1)
}

mutating func siftUp(from index: Int) {
  var child = index
  var parent = parentIndex(ofChildAt: child)
  while child > 0 && sort(elements[child], elements[parent]) {
    elements.swapAt(child, parent)
    child = parent
    parent = parentIndex(ofChildAt: child)
  }
}

正如你所看到的，这个实现是非常直接的：

• insert将元素添加到数组中，然后执行sift up。
• siftUp将当前节点与它的父节点交换，只要该节点的优先级高于它的父节点。

Complexity

insert(_:)的总体复杂度是O(log n)。在数组中追加一个元素只需要O(1)，而在堆中筛选元素需要O(log n)。

这就是在堆中插入一个元素的全部内容。

到目前为止，你已经看了从堆中删除根元素和插入到堆中的问题。但是，如果你想从堆中删除任何任意的元素呢？

从一个任意索引中删除

在Heap中添加以下内容：

mutating func remove(at index: Int) -> Element? {
  guard index < elements.count else {
    return nil // 1
  }
  if index == elements.count - 1 {
    return elements.removeLast() // 2
  } else {
    elements.swapAt(index, elements.count - 1) // 3
    defer {
      siftDown(from: index) // 5
      siftUp(from: index)
    }
    return elements.removeLast() // 4
  }
}

要从堆中删除任何元素，你需要一个索引。让我们来看看这是如何进行的：

1. 检查索引是否在数组的范围内。如果不是，返回nil。
2. 如果你要删除堆中的最后一个元素，你不需要做任何特别的事情。只需删除并返回该元素。
3. 如果你不删除最后一个元素，首先将该元素与最后一个元素交换。
4. 然后，返回并删除最后一个元素。
5. 最后，进行下筛和上筛来调整堆。

但是--为什么你必须同时执行下筛和上筛？

假设你想删除5。你把5和最后一个元素交换，也就是8。你现在需要执行一个上筛以满足最大堆属性。

现在，假设你想删除7。你将7与最后一个元素1交换。你现在需要进行筛选，以满足最大堆属性。

从堆中删除一个任意元素是一个O(log n)的操作。但是你如何找到你想删除的元素的索引呢？

在堆中搜索一个元素

为了找到你想删除的元素的索引，你必须在堆中进行搜索。不幸的是，堆并不是为快速搜索而设计的。使用二进制搜索树，你可以在O(log n)时间内进行搜索，但是由于堆是使用数组建立的，而数组中的节点排序是不同的，你甚至不能进行二进制搜索。

Complexity

在堆中搜索一个元素，在最坏的情况下，是一个O(n)的操作，因为你可能要检查数组中的每个元素：

func index(of element: Element, startingAt i: Int) -> Int? {
  if i >= count {
    return nil // 1
  }
  if sort(element, elements[i]) {
    return nil // 2
  }
  if element == elements[i] {
    return i // 3
  }
  if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
    return j // 4
  }
  if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
    return j // 5
  }
  return nil // 6
}

让我们来看看这个执行情况：

1. 如果索引大于或等于数组中的元素数，则搜索失败。返回nil。
2. 检查你要找的元素是否比索引i处的当前元素有更高的优先级。如果是的话，你要找的元素不可能在堆中处于较低位置。
3. 如果该元素与索引i处的元素相等，则返回i。
4. 从i的左边的孩子开始，递归搜索该元素。
5. 递归搜索从i的右边的孩子开始的元素。
6. 如果两个搜索都失败了，说明搜索失败。返回nil。

Note

虽然搜索需要O(n)时间，但你已经通过利用堆的属性和搜索时检查元素的优先级来努力优化搜索。

构建一个堆

你现在已经拥有了表示一个堆的所有必要工具。为了总结本章，你将从一个现有的元素数组中建立一个堆并对其进行测试。更新Heap的初始化器，如下：

init(sort: @escaping (Element, Element) -> Bool,
     elements: [Element] = []) {
  self.sort = sort
  self.elements = elements

  if !elements.isEmpty {
    for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
      siftDown(from: i)
    }
  }
}

初始化器现在需要一个额外的参数。如果提供了一个非空的数组，你就用它作为堆的元素。为了满足堆的属性，你从第一个非叶子节点开始，向后循环数组，并向下筛选所有的父节点。你只循环了一半的元素，因为筛选leaf节点没有意义，只有父节点。

测试

是时候试试了。在你的Playground上添加以下内容：

var heap = Heap(sort: >, elements: [1,12,3,4,1,6,8,7])

while !heap.isEmpty {
  print(heap.remove()!)
}

这个循环创建了一个最大的堆，因为>被用作排序谓词，并逐一移除元素，直到它为空。注意元素从大到小被移除，以下数字被打印到控制台。

12
8
7
6
4
3
1
1

关键点

• 下面是对你在本章中实现的堆操作的算法复杂性的总结：

• 堆数据结构有利于维护最高或最低优先级的元素。
• 堆中的元素被打包到连续的内存中，使用一个简单的公式进行元素查找。
• 每次你插入或删除项目时，你必须注意保留堆的属性。