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

特性

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

第一特性，堆结构是存储在数组中的。

堆通过 priority 优先事项进行排序，可以分为，max-priority(最高优先级)、和 max-priority(最低优先级)两种

二叉搜索树中，有left<parent<right 的特性，但是在堆中，只是只能保证孩子一定是小于或大于父节点的。

二叉树在存储的过程中需要更多的内存，因为节点需要存储指向父节点，子节点等的指针，但是堆不需要，他存储在数组中

二叉树中的一些特别树，如红黑树，AVL树等，删除，插入，及搜索的多度都很快，但是，堆结构的搜索相对来说会慢很多，但是堆结构对于查找，最大或者最小等需求时，查找速度是很快的。

堆有一个很重要的特性，就是只有在上一层完全满之后，才能到下一层来进行存储，不允许中间某个节点的子节点为空，因为是通过数组存储的嘛

前面说过堆结构实际存储在数组中，他具体的形式如下

从上面的图中可以推导出，一个重要的公式：节点 node 的孩子在数组中的位置：左孩子：index = 2 * i + 1 右孩子：index = 2 * i + 2 其中i为当前节点n在数组中的下标

插入及删除

堆结构的插入及删除操作的基本思路如下：

插入：插入时一定是从最后面开始插入，类似入队操作，插入后，用新节点和父节点比，如果优先级大于父节点，则和父节点交互位置后，继续和新的父节点比较，依次类推

删除：删除通常为删除最大的节点，即根节点，过程为，先将根节点和最后面的节点互换位置后，在删除最后面的节点，即原来的根节点，然后用根节点和子节点向下进行比较，如果小于子节点，则互换位置，依次类推。时刻谨记，堆结构是存储在数组中的。

实现

struct Heap
    
      {    ///存放元素的数组    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)    }}复制代码