Swift로 구현한 힙

Swift로 우선순위 큐를 구현하려면 직접 힙을 구현해야한다. 여기 Swift로 구현한 힙이 있습니다. 찾은 자료중 가장 깔끔한것 같아요.

final class Heap<T: Comparable> {
    private var nodes: [T] = []
    private let sort: (T, T) -> Bool

    init(sort: @escaping ((T, T) -> Bool)) {
        self.sort = sort
    }

    var isEmpty: Bool {
        nodes.isEmpty
    }

    func insert(_ data: T) {
        var index = nodes.count
        nodes.append(data)

        while index >= 0, sort(nodes[index], nodes[(index-1) / 2]) {
            nodes.swapAt(index, (index - 1) / 2)
            index = (index-1) / 2
        }
    }

    func delete() -> T {
        if nodes.count == 1 {
            return nodes.removeFirst()
        }

        let data = nodes.first!
        nodes.swapAt(0, nodes.count - 1)
        nodes.removeLast()

        let limit = nodes.count
        var index = 0

        while index < limit {
            let leftChild = index * 2 + 1
            let rightChild = leftChild + 1

            let children = [leftChild, rightChild]
            .filter { $0 < limit && sort(nodes[$0], nodes[index]) }
            .sorted { sort(nodes[$0], nodes[$1]) }

            if children.isEmpty { break }
            nodes.swapAt(index, children.first!)
            index = children.first!
        }

        return data
    }
}

let heap = Heap<Int>(sort: < )

Uploaded by N2T