Heap(堆结构/优先队列)-Swift实现

特性

堆

堆结构很像二叉树，堆也是一个近似树形结构，堆的每个节点也最多有左、右两个孩子，但是堆实质是存储在数组中的结构，所以他和二叉树只是近似的有某些共同的特性。

• 第一特性，堆结构是存储在数组中的。
• 堆通过 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)
    }
}