스위프트에서 바이너리 힙 구현하기

바이너리 힙은 선형 리스트에 이진트리형식의 데이터를 저장하는 재밌는 방식의 데이터 타입이다. 이 구조에서는 리스트(배열) 내의 원소의 위치를 맞바꾸는 동작이 빈번하게 일어나므로, 아예 배열에서 원소를 바꾸는 동작을 추가해 주도록 하자.

extension Array {
    mutating func swapElement(#at:Int, with:Int) {
        let fromElement = self[with]
        self[with] = self[at]
        self[at] = fromElement
    }
}

그리고 다음과 같이 구현된다. 파이썬 보다 쉬운 듯?

class BinaryHeap<T:Comparable> {
    var items:Array<T?> = [nil]
    var currentSize = 0
    var isEmpty:Bool {
        return currentSize == 0
    }
    func enqueue(item:T) {
        items.append(item)
        self.percUp(from: ++currentSize)
    }
    func percUp(var from i:Int) {
        /*
        새로 추가된 원소는 자신의 부모 (i/2 번째 원소)와 비교하여,
        부모보다 작으면 부모와 자리를 바꾸고, 이 상태로 1번 위치까지 올라간다.
        즉, 가장 작은 원소가 추가되면 큐의 가장 앞으로 올라간다.
        */
        while i > 0 {
            if items[i] < items[i/2] {
                items.swapElement(at: i, with: i/2)
            }
            i = i / 2
        }
    }
    func percDown(var from i:Int) {
        while (i*2) <= currentSize {
            let mc = self.findMinimumChild(from: i)
            if items[i] > items[mc] {
                items.swapElement(at: i, with: mc)
            }
            i = mc
        }
    }
    func dequeue() -> T {
        let ret = items[1]
        items[1] = items.last!
        items.removeLast()
        --currentSize
        self.percDown(from: 1)
        return ret!
    }
    func findMinimumChild(var from i:Int)->Int {
        if i * 2 + 1 > currentSize {
            return i * 2
        } else if items[i * 2] < items[i * 2 + 1] {
            return i * 2
        } else {
            return i * 2 + 1
        }
    }
}
var intBinaryHeap = BinaryHeap<Int>()
intBinaryHeap.enqueue(8)
intBinaryHeap.enqueue(5)
intBinaryHeap.enqueue(9)
intBinaryHeap.enqueue(12)
intBinaryHeap.enqueue(4)
intBinaryHeap.enqueue(1)
intBinaryHeap.enqueue(6)
while !intBinaryHeap.isEmpty {
    println(">> \(intBinaryHeap.dequeue())")
}
var strBinHeap = BinaryHeap<String>()
strBinHeap.enqueue("foo")
strBinHeap.enqueue("bar")
while !strBinHeap.isEmpty {
    println(">> \(strBinHeap.dequeue())")
}