在本教程中，我们将讨论并在Swift中实现Heap数据结构。

Swift堆

堆可以是最大堆，也可以是最小堆。
在最大堆中，根节点是最大的元素，所有子节点必须小于父节点。
最小堆的工作方式恰恰相反。
堆是一种特殊的基于树的数据结构。
堆数据结构可用于有效地找到数组中第k个最小(或者最大)的元素。

堆属性：如果P是C的父节点，则P的键(值)大于或者等于(在最大堆中)或者小于或者等于(在最小堆中)C的键。

顶部的节点是最高优先级的节点。

堆化

删除元素需要重新排列堆数据结构。
这称为堆化。

例如，如果删除堆的根节点。
为此，我们需要将其与根节点之间的最低节点交换，然后在整个过程中递归检查堆属性。

heapifyUp()从底部开始，并一直检查堆属性。

heapifyDown()恰好相反

N处的节点的子代将在最大堆中定位为" 2n + 1"和" 2n + 2"。

让我们启动XCode运动场，并使用Swift创建我们的堆。
我们将使用数组构建堆结构。

建立一个堆

struct Heap<T> {
  var elements = [T]()
  
  var isEmpty: Bool { return elements.isEmpty }
  var count: Int { return elements.count }
  var isOrdered: (T, T) -> Bool
  
  public init(sort: @escaping (T, T) -> Bool) {
      self.isOrdered = sort
  }

}

传递了转义的闭包，用于保存函数值。
它比较传递的两个值。

在结构中添加以下函数以获取父节点，左节点和右节点的索引：

func parentOf(_ index: Int) -> Int {
      return (index - 1)/2
  }
  func leftOf(_ index: Int) -> Int {
      return (2 * index) + 1
  }
  func rightOf(_ index: Int) -> Int {
      return (2 * index) + 2
  }

heapifyDown()：

mutating func heapifyDown(index: Int, heapSize: Int) {

      var parentIndex = index
      
      while true {
          let leftIndex = self.leftOf(parentIndex)
          let rightIndex = leftIndex + 1
          
          var first = parentIndex
          if leftIndex < heapSize && isOrdered(elements[leftIndex], elements[first]) {
              first = leftIndex
          }
          if rightIndex < heapSize && isOrdered(elements[rightIndex], elements[first]) {
              first = rightIndex
          }
          if first == parentIndex { return }
          
          elements.swapAt(parentIndex, first)
          parentIndex = first
      }
  }

mutating func shiftDown() {
      heapifyDown(index: 0, heapSize: elements.count)
  }

在删除元素时使用heapifyDown()。
插入时使用heapifyUp()。

以下函数用于从数组构建堆：

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

heapifyUp()：

mutating func heapifyUp(index: Int) {
      var nodeIndex = index
      
      while true {
          let parentIndex = self.parentOf(nodeIndex)
          
          var first = parentIndex
          if parentIndex >= 0 && isOrdered(elements[nodeIndex], elements[first]) {
              first = nodeIndex
          }
          if first == parentIndex { return }
          

          elements.swapAt(parentIndex, first)
          nodeIndex = first
      }
  }

以下函数用于从堆中插入和删除元素：

插入：

mutating func insert(value: T) {
      self.elements.append(value)
      
      heapifyUp(index: self.elements.count - 1)
  }

删除：

public mutating func remove(at index: Int) -> T? {
      let temp: T
      
      if index < 0 && count - 1 <= index {
          return nil
      }
      temp = elements[index]
      elements[index] = elements[count - 1]
      elements.removeLast()
      shiftDown()
      return temp
  }

让我们使用示例输入来测试我们创建的上述结构：

let array: [Int] = [12,3,6,15,45,1,2]
var heap = Heap<Int>(sort: >)
heap.buildHeap(fromArray: array)
heap.insert(value: 23)
print(heap.elements)
print(heap.remove(at: 0))
print(heap.elements)