[Swift] 우선순위 큐(Priority Queue) 구현해보기

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다.

이 글의 모든 출처는 https://jeonyeohun.tistory.com/327 이곳에 있습니다.

우선순위 큐(Priority Queue)

힙을 이용해서 가장 높은 우선순위에 있는 요소를 항상 제일 처음에 위치시키는 특별한 큐

가장 우선순위가 높은 요소가 큐에서 제거되면 그 다음 우선순위에 있는 요소가 큐의 첫 요소로 이동합니다.

힙에 대한 설명은 https://jerry311.tistory.com/55 에 있습니다.

 

우선순위 설정

우선순위 큐를 사용하려면 어떤 기준으로 우선순위를 정할지 지정해주어야 합니다.

지정

init(_ elements: [T] = [], _ sort: @escaping (T, T) -> Bool) {
    heap = Heap(elements: elements, sortFunction: sort)
}

이 때문에 생성자에 2개의 인자를 받아 Bool 값을 반환하는 클로저를 받아주어야 합니다.

Swift에서 등호연산도 함수이기 때문에 아래처럼 사용할 수 있습니다.

사용

var pq = PriorityQueue(<)

 

삽입(push) - O(logN)

우선순위 큐의 삽입은 힙에 새로운 노드를 삽입하는 것과 동일합니다.

힙에 새로운 노드를 삽입하면 이진트리의 가장 마지막 노드를 붙이고 부모노드보다 우선순위가 작을 때까지 부모노드와의 교환을 계속 반복하면서 트리를 거슬러 올라가는 과정을 거쳐야했습니다.

 

따라서 힙의 삽입과 동일한 시간복잡도인 O(logN)이 요구됩니다.

mutating func push(_ element: T) {
    heap.insert(node: element)
}

 

삭제(pop) - O(logN)

우선순위 큐의 삭제연산 역시도 힙의 삭제 연산과 동일합니다.

어떤 특정요소를 삭제하는 것은 허용되지 않고, 가장 우선순위가 높은 루트노드를 삭제해 반환합니다.

힙에서 루트노드를 삭제하는 것은 루트노드와 마지막 리프노드의 값을 교환한 뒤에 리프노드를 제거해 반환하고 루트노드로부터 힙을 재조정해주는 것으로 이루어집니다.

 

따라서 힙의 삭제와 동일한 시간복잡도인 O(logN)이 요구됩니다.

 

전체 코드

struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    
    init(_ elements: [T] = [], _ sort: @escaping (T, T) -> Bool) {
        heap = Heap(elements: elements, sortFunction: sort)
    }
    
    var count : Int {
        return heap.count
    }
    var isEmpty : Bool {
        return heap.isEmpty
    }
    
    func top () -> T? {
        return heap.peek
    }
    mutating func clear () {
        while !heap.isEmpty {
            _ = heap.remove()
        }
    }
    mutating func pop() -> T? {
        return heap.remove()
    }
    mutating func push(_ element: T) {
        heap.insert(node: element)
    }
}