Swift 数据结构与算法实现

用 Swift 实现了 Trie 字典树、并查集、堆和优先队列、哈希表、红黑树、集合与映射、链表、数组、栈、队列、线段树、AVL 树等。
课程是慕课网的：
玩转算法系列--数据结构精讲 更适合0算法基础入门到进阶（java版）
Github 链接
给有需要的朋友做个参考。
最大堆示例代码

class MaxHeap<T: Comparable> {
    private var array: Array<T>
    
    init(capacity: Int) {
        self.array = Array<T>.init()
        self.array.reserveCapacity(capacity)
    }
    
    convenience init() {
        self.init(capacity: 10)
    }
    
    convenience init(array: Array<T>) {
        self.init(capacity: array.count)
        for i in (0...parent(index: array.count - 1)).reversed() {
            var k = i
            siftDown(k: &k)
        }
    }
    
    func getSize() -> Int {
        return array.count
    }
    
    func isEmpty() -> Bool {
        return array.isEmpty
    }
    
    private func parent(index: Int) -> Int {
        if index == 0 {
            fatalError("0 no parent!")
        }
        return (index - 1) / 2
    }
    
    private func leftChild(index: Int) -> Int {
        return index * 2 + 1
    }
    
    private func rightChild(index: Int) -> Int {
        return index * 2 + 2
    }
    
    func add(element: T) {
        array.append(element)
        var k = getSize() - 1
        siftUp(k: &k)
    }
    
    private func siftUp(k: inout Int) {
        while k > 0 && array[k] > array[parent(index: k)] {
            array.swapAt(k, parent(index: k))
            k = parent(index: k)
        }
    }
    
    func findMax() -> T {
        if array.isEmpty {
            fatalError("heap is empty!")
        }
        return array[0]
    }
    
    func extractMax() -> T {
        let max = findMax()
        array[0] = array[getSize() - 1]
        array.removeLast()
        var k = 0
        siftDown(k: &k)
        return max
    }
    
    private func siftDown(k: inout Int) {
        var j = 0
        while leftChild(index: k) < getSize() {
            j = leftChild(index: k)
            if rightChild(index: k) < getSize() && array[j] < array[j + 1] {
                j = rightChild(index: k)
            }
            if array[k] < array[j] {
                array.swapAt(k, j)
            }
            k = j
        }
    }
    
    func replace(element: T) -> T {
        let max = findMax()
        array[0] = element
        var k = 0
        siftDown(k: &k)
        return max
    }
}