[Algorithm] 우선 순위 큐 Swift 구현

[Algorithm] 우선 순위 큐 Swift 구현

 

익히 알려져 있다시피 Swift는 우선 순위 큐가 구현되어 있지 않다. 직접 구현을 해야 우선순위 큐를 활용할 수 있는데 코딩테스트를 볼 때 이는 굉장히 귀찮음으로 다가온다. 미리 기록해놓고 나중에 써먹던지.. 다시와서 보는 용도로 포스팅을 한다.

 

import Foundation

struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    var count : Int {
        return heap.count
    }
    var isEmpty : Bool {
        return heap.isEmpty
    }
    
    init(_ elements: [T] = [], _ sort: @escaping (T, T) -> Bool) {
        heap = Heap(elements: elements, sortFunction: sort)
    }
    
    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)
    }
}

 

*설명

 

Heap 구조체를 기반으로 우선순위 큐를 구현한다. Heap 구조체는 우선순위에 따라 요소를 정렬하고, 이진 트리 형태로 구현된다. Heap은 주어진 요소를 추가하거나 제거하고, 최상위 요소에 접근할 수 있는 기능을 가지고 있다.

 

PriorityQueue 구조체는 이 Heap을 내부에 포함하고 있다. Heap을 사용하여 우선순위 큐의 핵심 기능을 사용하는 것이다.

 

init 메서드는 우선순위 큐를 초기화한다. 이 때, 초기 요소들과 정렬 함수를 받아 힙을 초기화한다.

top 메서드는 우선순위 큐의 최상위 요소를 반환한다.

clear 메서드는 우선순위 큐를 비운다.

pop 메서드는 우선순위 큐에서 최상위 요소를 제거하고 반환한다.

push 메서드는 우선순위 큐에 요소를 추가한다.