Swift 우선순위 큐(Priority Queue) 구현

우선순위 큐(Priority Queue)

• 힙을 이용해서 가장 높은 우선순위에 있는 요소를 제일 처음에 위치시키는 자료구조이다.
• 가장 우선순위가 제거되면, 그다음으로 높은 우선순위인 요소가 앞에 위치하게 된다.
• 구현을 위해서 힙이 구현되어있어야 한다.
• 우선순위큐의 삽입 삭제 시간복잡도는 O(logN)으로 일반 배열을 사용하는 것보다 빠르다.

 

힙 (Heap) Swift 구현

https://jenikeju.tistory.com/129

Swift 힙(Heap) 구현

 

 

우선순위 큐 구현코드

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)
    }
}