swift PriorityQueue 구현

swift로 우선순위 큐를 구현했습니다.

/*
 base on : Array, binary Tree
 */
class PriorityQueue<T: Comparable>{
    private var elements: [T] = []
    private let compare: (T, T) -> Bool
    var top: T?{elements.first}
    var isEmpty: Bool{elements.isEmpty}
    var count: Int{elements.count}
    init(){
        compare = {$0 < $1} // closure인데, 기본값은 오름차순이다
    }
    init(criteria compare:@escaping (T, T) -> Bool){
        self.compare = compare // 정렬 기준을 받아서 덮어쓰기
    }
    func push(_ element: T){//상단에 두고 아래로 내리면 된다.
        //오른쪽 왼쪽 보면서 내려값시다
        //1. 일단 제일 마지막의 인덱스를 갖고 온다.
        //2. 자신의 부모와 비교하여 올라간다.
        elements.append(element)//제일 마지막으로 넣고
        var now: Int = elements.count - 1 //현재 제일 마지막 인덱스 갖고 오기
        while now > 0 {
            let parent: Int = (now-1) / 2//부모 노드 idx 알아 내기
            guard compare(elements[now],elements[parent]) else{break}
            elements.swapAt(now, parent)
            now = parent//부모 idx로 변환
        }
    }
    func pop() -> T?{
        guard self.count != 0 else{ return nil}
        //1. 제일 위에 있는 탑을 갖고 오고
        //2. 제일 마지막에 있는 벨류를 삭제합니다.
        //3. 벨류가 맨 위에 있다고 생각하고
        //4. 하나하나 자식 인덱스와 비교하여 내려가시면 됩니다.
        let ret: T? = elements.first
        elements.swapAt(0, self.count - 1)
        elements.removeLast()//마지막 값 없애주기
        
        var parent: Int = 0
        var child: Int = 1
        while child < self.count{//
            if child + 1 < self.count, compare(elements[child + 1],elements[child]){
                child += 1
            }
            guard compare(elements[child],elements[parent]) else {break}
            elements.swapAt(parent, child)
            parent = child
            child = parent*2 + 1
        }
        return ret
    }
}

 

사용 방법은 다음과 같습니다.

var pq: PriorityQueue<Int> = PriorityQueue{$0 > $1}
pq.push(1)
pq.push(2)
pq.push(6)
pq.push(9)
while let top = pq.pop(){
    print(top)
}

 

기본으로 제공되는 자료형 같은 경우 생성해서 바로 사용하셔도 되고, 또는 매개변수로 새로운 정렬 기준을 넣어주면서 생성하셔갖고 사용하시면 됩니다.

 

만약 새로운 구조체나 클래스로 우선순위큐를 만든다고 했을 시에는 다음과 같이 사용하시면 됩니다.

struct Pair{
    let first: Int
    let second: Int
}
extension Pair: Comparable{
    static func < (lhs: Pair, rhs: Pair) -> Bool {
        if lhs.first == rhs.first{
            return lhs.second < rhs.second
        }
        return lhs.first < rhs.first
    }
}
var pairPq = PriorityQueue<Pair>()
pairPq.push(Pair(first: 1, second: 3))
pairPq.push(Pair(first: 9, second: 1))
pairPq.push(Pair(first: 8, second: 2))
pairPq.push(Pair(first: 7, second: 4))

while let top = pairPq.pop(){
    print(top)
}

 

Comparable 프로토콜을 채택을 한 구조체, 클래스를 만들고 우선순위큐를 만드시면 됩니다.

 

우선순위큐에서 사용하실 수 있는 커맨드는 다음과 같습니다.

1. isEmpty

2. push()
3. pop()
4. count

5. top

 

1번은 말 그대로 비어있는지 파악한 뒤 bool 값을 리턴해줍니다.

2번은 element를 넣어주시면 됩니다.

3번은 top이 빠지며 그 값이 리턴되게끔 만들었습니다.

4번은 현재 우선순위큐의 사이즈입니다.

5번은 top의 값은 리턴 해줍니다.