스위프트로 구현하는 자료구조 6: 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

우선순위 큐는 힙을 이용해서 가장 높은 우선순위의 있는 요소를 항상 제일 처음에 위치시키는 특별한 큐입니다. 가장 우선순위가 높은 요소가 큐에서 제거되면 그 다음 우선순위에 있는 요소가 큐의 첫 요소로 이동합니다. 

사실 우선순위 큐는 힙이 전부인 자료구조이기 때문에 힙을 아직 모르신다면 아래 포스트를 먼저 읽어주세요!

스위프트로 구현하는 자료구조 5: 힙(Heap)

우선순위 설정

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

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

이 때문에 이렇게 생성자에 두 개의 인자를 받아 Bool 값을 반환하는 클로저를 받아주어야 합니다. 스위프트에서 등호연산도 역시 함수이기 때문에 아래와 같이 사용할 수 있습니다.

var pq = PriorityQueue(<)

 

삽입(push) - O(logN)

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

 

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

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

 

삭제(pop) - O(logN)

우선순위 큐의 삭제 연산 역시도 힙의 삭제 연산과 동일합니다. 어떤 특정 요소를 삭제하는 것은 허용되지 않고, 가장 우선순위가 높은 루트노드를 삭제해 반환합니다. 힙에서 루트노드를 사제하는 것은 루트 노드와 마지막 리프노드의 값을 교환한 뒤에 리프노드를 제거해 반환하고 루트노드부터 힙을 재조정해주는 것으로 이루어집니다.

 

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

    mutating func pop() -> T? {
        return heap.remove()
    }

 

전체 코드

 

GitHub - jeonyeohun/Data-Structures-In-Swift: 👷🏻‍♂️ STL 왜 없어.. 스위프트로 구현하는 자료구조

자료구조 시리즈의 코드들은 이 레포에서 모두 확인할 수 있어요!