特性
堆
堆结构很像二叉树，堆也是一个近似树形结构，堆的每个节点也最多有左、右两个孩子，但是堆实质是存储在数组中的结构，所以他和二叉树只是近似的有某些共同的特性。
- 第一特性，堆结构是存储在数组中的。
- 堆通过 priority 优先事项进行排序，可以分为，max-priority(最高优先级)、和 max-priority(最低优先级)两种
- 二叉搜索树中，有left<parent<right 的特性，但是在堆中，只是只能保证孩子一定是小于或大于父节点的。
- 二叉树在存储的过程中需要更多的内存，因为节点需要存储指向父节点，子节点等的指针，但是堆不需要，他存储在数组中
- 二叉树中的一些特别树，如红黑树，AVL树等，删除，插入，及搜索的多度都很快，但是，堆结构的搜索相对来说会慢很多，但是堆结构对于查找，最大或者最小等需求时，查找速度是很快的。
- 堆有一个很重要的特性，就是只有在上一层完全满之后，才能到下一层来进行存储，不允许中间某个节点的子节点为空，因为是通过数组存储的嘛
前面说过堆结构实际存储在数组中，他具体的形式如下
树形结构
实际存储
从上面的图中可以推导出，一个重要的公式：
节点 node 的孩子在数组中的位置：
左孩子：index = 2 * i + 1
右孩子：index = 2 * i + 2
其中i为当前节点n在数组中的下标
插入及删除
堆结构的插入及删除操作的基本思路如下：
- 插入： 插入时一定是从最后面开始插入，类似入队操作，插入后，用新节点和父节点比，如果优先级大于父节点，则和父节点交互位置后，继续和新的父节点比较，依次类推
- 删除：删除通常为删除最大的节点，即根节点，过程为，先将根节点和最后面的节点互换位置后，在删除最后面的节点，即原来的根节点，然后用根节点和子节点向下进行比较，如果小于子节点，则互换位置，依次类推。
时刻谨记，堆结构是存储在数组中的。
实现
struct Heap<Element> {
///存放元素的数组
var elements: [Element]
//比较两个元素大小的方法
let priorityFunction: (Element, Element) -> Bool
init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) { // 1 // 2
self.elements = elements
self.priorityFunction = priorityFunction // 3
buildHeap() // 4
}
mutating func buildHeap() {
for index in (0 ..< count / 2).reversed() { // 5
siftDown(index) // 6
}
}
var isEmpty : Bool {
return elements.isEmpty
}
var count : Int {
return elements.count
}
func peek() -> Element? {
return elements.first
}
func isRoot(_ index: Int) -> Bool {
return (index == 0)
}
///当前节点的左孩子
func leftChildIndex(of index: Int) -> Int {
return (2 * index) + 1
}
///当前节点的右孩子
func rightChildIndex(of index: Int) -> Int {
return (2 * index) + 2
}
///当前节点的父节点
func parentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
//插入
mutating func equeue(_ element: Element) {
elements.append(element)
siftUP(elementAtIndex: elements.count - 1)
}
//删除
mutating func dequeue() -> Element? {
//判空
guard !isEmpty else { return nil }
//将第一个节点和最后一个节点交换位置
swapElement(at: 0, with: count - 1)
//删除原本的第一个，现在的最后一个
elements.removeLast()
guard !isEmpty else { return nil }
//向下判断，新的节点是不是优先级最高的节点
return nil
}
}
private extension Heap {
func isHigherPriority(firstIndex: Int, secondIndex: Int) -> Bool{
return priorityFunction(elements[firstIndex], elements[secondIndex])
}
func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
guard childIndex < count && isHigherPriority(firstIndex: childIndex, secondIndex: parentIndex)
else { return parentIndex }
return childIndex
}
func highestPriorityIndex(for parent: Int) -> Int {
return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
}
mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
guard firstIndex != secondIndex
else { return }
elements.swapAt(firstIndex, secondIndex)
}
mutating func siftDown(_ elementIndex: Int) {
//从当前节点及子节点中找出优先级最高的节点
let highestIndex = highestPriorityIndex(for: elementIndex)
//如果当前节点就是优先级最高的节点，直接放回
if highestIndex == elementIndex { return }
//如果不是优先级最高的节点，和优先级最高的节点对换位置
swapElement(at: elementIndex, with: highestIndex)
//从新的节点开始递归的向下判断优先级
siftDown(highestIndex)
}
mutating func siftUP(elementAtIndex: Int) {
//获得父节点的索引
let parentIndex = self.parentIndex(of: elementAtIndex)
//如果当前节点不是根节点，比较当前节点和父节点的优先级
guard !isRoot(elementAtIndex), isHigherPriority(firstIndex: elementAtIndex, secondIndex: parentIndex) else {
return
}
//如果当前节点的优先级高于父节点，兑换位置
swapElement(at: elementAtIndex, with: parentIndex)
//递归的从新的父节点开始向上比较
siftUP(elementAtIndex: parentIndex)
}
}
