算法-手动实现大顶堆、小顶堆

在刷LeetCode时，经常看到Java系统函数PriorityQueue。swift中没有，只能手动构造一个了。堆相关题目还是不少，要好好掌握。

提供一个父类

class PriorityQueue {
    var heap = [Int]()

    init(_ heap:[Int]) {
        self.heap = heap
    }
    
    func count() -> Int {
        return heap.count
    }
    
    func top() -> Int{
        return self.heap.first
    }
    
    func isEmpty() -> Bool {
        return self.heap.count == 0
    }
}

大顶堆

//大顶堆
class MaxPriorityQueue:PriorityQueue {
    
    override init(_ heap:[Int]) {
        super.init(heap)
        
        if heap.count == 0 {
            return
        }
        //构建大顶堆
        for i in (0...heap.count/2).reversed() {
            heapAdjust(&self.heap, i, heap.count)
        }
    }
    
    //上浮法:把新元素插入堆尾,向上逐层比较,上浮到合适的位置
    func add(_ val:Int) {
        self.heap.append(val)//插入尾部
        
        var childIndex = self.heap.count-1
        var parentIndex = (childIndex-1)/2
        while parentIndex>=0 && heap[childIndex]>heap[parentIndex] {
            heap.swap(childIndex, parentIndex)
            childIndex = parentIndex
            parentIndex = (childIndex-1)/2
        }
        
    }
    
    //弹出堆顶元素:用尾部元素放到堆顶,调整
    func poll() -> Int {
        if self.heap.count == 0 {
            return 0
        }
        let topVal = self.heap.first!
        
        self.heap[0] = self.heap.last!
        self.heap.removeLast()
        if heap.count>1 {//0或1个不用调整
            heapAdjust(&self.heap, 0, self.heap.count)
        }
        
        return topVal
    }
    
    //大顶堆
    func heapAdjust(_ array:inout [Int], _ parent:Int,_ length:Int) {
        var parentIndex = parent
        let temp = array[parentIndex]
        var child = 2*parentIndex+1//2n+1:左孩子,2n+2:右孩子
        //把最小的数据放在大于孩子节点的位置
        while child<length {
            //取左右孩子节点的最大节点
            if child+1<length && array[child]<array[child+1]{
                child += 1
            }
            if temp>array[child]{//父节点大于左右孩子节点
                break
            }
            array[parentIndex] = array[child]
            parentIndex = child
            
            child = 2*child+1
        }
        array[parentIndex] = temp
    }
    
}

1. 初始化时:堆的调整。只要处理一半的数据。把大的数据浮到顶部。在堆排序中也有用到。
2. add:添加元素。
   上浮法:把新元素插入堆尾,向上逐层比较,上浮到合适的位置
3. poll:弹出元素
   弹出堆顶元素:用尾部元素放到堆顶,调整

小顶堆

//小顶堆
class MinPriorityQueue:PriorityQueue {
    
    override init(_ heap:[Int]) {
        super.init(heap)
        
        if heap.count == 0 {
            return
        }
        //构建大顶堆
        for i in (0...heap.count/2).reversed() {
            heapAdjust(&self.heap, i, heap.count)
        }
    }
    
    //上浮法:把新元素插入堆尾,向上逐层比较,上浮到合适的位置
    func add(_ val:Int) {
        self.heap.append(val)//插入尾部
        
        var childIndex = self.heap.count-1
        var parentIndex = (childIndex-1)/2
        while parentIndex>=0 && heap[childIndex]<heap[parentIndex] {
            heap.swap(childIndex, parentIndex)
            childIndex = parentIndex
            parentIndex = (childIndex-1)/2
        }
        
    }
    
    //弹出堆顶元素:用尾部元素放到堆顶,调整
    func poll() -> Int {
        if self.heap.count == 0 {
            return 0
        }
        let topVal = self.heap.first!
        
        self.heap[0] = self.heap.last!
        self.heap.removeLast()
        if heap.count>1 {//0或1个不用调整
            heapAdjust(&self.heap, 0, self.heap.count)
        }
        
        return topVal
    }
    
    //小顶堆
    func heapAdjust(_ array:inout [Int], _ parent:Int,_ length:Int) {
        var parentIndex = parent
        let parentVal = array[parentIndex]
        var child = 2*parentIndex+1//2n+1:左孩子,2n+2:右孩子
        //把最小的数据放在大于孩子节点的位置
        while child<length {
            //取左右孩子节点的最大节点
            if child+1<length && array[child]>array[child+1]{
                child += 1
            }
            if parentVal<array[child]{//父节点大于左右孩子节点
                break
            }
            array[parentIndex] = array[child]
            parentIndex = child
            
            child = 2*child+1
        }
        array[parentIndex] = parentVal
    }
}

小顶堆与大顶堆类似，调整堆时判断条件需要改变下。

总结

1. 堆在算法中用的比较多。下面推荐几道算法题，上面代码可以直接应用。
   295. 数据流的中位数
   621. 任务调度器
   659. 分割数组为连续子序列
   767. 重构字符串
   1046. 最后一块石头的重量
   1202. 交换字符串中的元素