利用数组实现堆

成员变量

元素个数N
包含元素的数组items

方法

插入
删除

插入实现

1 将元素直接插入到最后一个元素（N），N从1开始
2 使用上浮，将最后一个元素上浮到合适位置

上浮实现

比较N处元素和其父节点的大小，如果大，则交换两者的位置，直到N处元素变为第1个元素

删除实现

1 将1处元素（根节点）和N处元素交换，同时将交换的N处元素置空
2 通过下沉，让1处元素处于合适位置

下沉

通过循环比较父节点和其左右子树的大小，如果父节点比其左右子树中较大者小，则交换两者位置，直到这个父节点没有左右子树

代码

/// 堆
class Heap {
    
    private var items = [String]()
    /// 堆中元素个数
    var N = 0
    
    init(capacity: Int) {
        for _ in 0..<capacity {
            items.append("")
        }
    }
    
    func printHeap() {
        for i in 0..<N {
            print("\(items[i])")
        }
    }
    
    /// i处元素是否比j处元素小
    private func less(i: Int, j: Int) -> Bool {
        if items[i].compare(items[j]) == .orderedAscending {
            return true
        } else {
            return false
        }
    }
    
    private func exchange(i: Int, j: Int) {
        let temp = items[i]
        items[i] = items[j]
        items[j] = temp
    }
    
    /// 插入元素
    func insert(t: String) {
        N = N + 1
        items[N] = t
        swim(k: N)
    }
    
    /// 上浮算法，让k处元素处于正确的位置
    private func swim(k: Int) {
        var i = k
        while i > 1 {
            if less(i: i/2, j: i) {
                exchange(i: i/2, j: i)
            }
            i = i / 2
        }
    }
    
    /// 删除最大元素
    func deleteMax() -> String {
        let maxItem = items[1]
        exchange(i: 1, j: N)
        items[N] = ""
        sink(k: 1)
        N = N - 1
        return maxItem
    }
    
    /// 下沉算法，让k处元素处于正确的位置
    private func sink(k: Int) {
        var i = k
        while 2*i <= N {
            var max = 2*i
            if 2*i+1 <= N {   // 如果有右子树
                if less(i: 2*i, j: 2*k+1) {
                    max = 2*i+1
                }
            }
            if !less(i: i, j: max) {
                break
            }
            exchange(i: i, j: max)
            i = max
        }
    }
}

demo地址：https://github.com/yangguanghei/studyDateStructure