23.堆的挑战¶

你认为你已经掌握了堆的知识？在本章中，你将探索与堆有关的四个不同问题。这些问题的作用是巩固你对数据结构的基本知识。

挑战1: 找出第n个最小的整数¶

写一个函数，找出未排序数组中最小的nth个整数。例如：

let integers = [3, 10, 18, 5, 21, 100]

如果n = 3，结果应该是10。

挑战2：分步示意图¶

给出以下数组，直观地构建一个最小堆。提供如何构建最小堆的分步图。

[21, 10, 18, 5, 3, 100, 1]

挑战3：合并两个堆¶

写一个结合两个堆的方法。

挑战4：最小堆？¶

写一个函数，检查一个给定的数组是否是最小堆。

解决方案¶

挑战1的解决方案¶

有很多方法可以解决未排序数组中最小的nth个整数的问题。例如，你可以选择本章所学的一种排序算法，对数组进行排序，然后抓取nth索引处的元素。

让我们来看看如何使用min-heap获得第nth个最小的元素!

func getNthSmallestElement(n: Int, elements: [Int]) -> Int? {
  var heap = Heap(sort: <, elements: elements) // 1
  var current = 1 // 2
  while !heap.isEmpty { // 3
    let element = heap.remove() // 4
    if current == n { // 5
      return element
    }
    current += 1 // 6
  }
  return nil // 7
}

让我们来看看解决方案：

用未排序的数组初始化一个迷你堆。
current跟踪第n个最小的元素。
只要堆不是空的，就继续删除元素。
从堆中删除根元素。
检查你是否达到了第n个最小的元素。如果是，则返回该元素。
如果不是，增加current。
如果堆是空的，返回nil。

建立一个堆需要O(n)。从堆中移除每个元素需要O(log n)。请记住，你也在做这个n次。总的时间复杂性是O(n log n)。

挑战2的解决方案¶

[21, 10, 18, 5, 3, 100, 1]

挑战3的解决方案¶

将此作为Heap.swift的一个附加函数：

mutating public func merge(_ heap: Heap) {
  elements = elements + heap.elements
  buildHeap()
}

合并两个堆是非常简单的。你首先合并两个数组，这需要O(m)，其中m是你要合并的heap的长度。建立堆需要O(n)。总的来说，该算法的运行时间为O(n)。

挑战4的解决方案¶

要检查给定的数组是否是最小堆，你只需要通过二进制堆的所有父节点。为了满足最小堆的要求，每个父节点必须小于或等于其左、右子节点。

下面是一些辅助方法，用于抓取给定的父索引的左和右子索引。

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

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

现在让我们看看如何确定一个数组是否是最小堆：

func isMinHeap<Element: Comparable>(elements: [Element]) -> Bool {
  guard !elements.isEmpty else { // 1
    return true
  }
  // 2
  for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
    let left = leftChildIndex(ofParentAt: i) // 3
    let right = rightChildIndex(ofParentAt: i)
    if elements[left] < elements[i] { // 4
      return false
    }
    if right < elements.count && elements[right] < elements[i]  { // 5
      return false
    }
  }
  return true // 6
}

如果数组是空的，它就是一个最小的堆!
以相反的顺序浏览数组中的所有父节点。
获得左和右的子节点索引。
检查左边的元素是否比父节点少。
检查右边的索引是否在数组的范围内，并检查右边的元素是否小于父元素。
如果每个父子关系都满足min-heap属性，则返回true!

这个解决方案的时间复杂性是O(n)。这是因为你仍然需要遍历数组中的每个元素。