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

우선순위 큐는 요소가 삽입될 때마다 우선순위에 따라 정렬되며, 가장 높은 우선순위의 요소가 먼저 처리됩니다.

 

이전에 구현한 Heap을 사용하여 우선순위 큐를 쉽게 구현할 수 있습니다.

아래는 PriorityQueue 구조체를 제네릭으로 정의한 코드입니다.

struct PriorityQueue<T> {
    private var heap: Heap<T>

    var isEmpty: Bool {
        return heap.isEmpty
    }

    var count: Int {
        return heap.count
    }

    var peek: T? {
        return heap.peek
    }
    
    init(sort: @escaping (T, T) -> Bool) {
        heap = Heap(priorityFunction: sort)
    }

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

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

 

위 코드에서는 우선순위 큐의 기본 동작을 구현했습니다.

 

 

• enqueue(_:): 우선순위 큐에 새 요소를 추가합니다. 시간 복잡도는 O(log n)입니다.
• dequeue(): 가장 높은 우선순위의 요소를 제거하고 반환합니다. 시간 복잡도는 O(log n)입니다.

 

우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐로 나눌 수 있습니다.

최소 우선순위 큐는 숫자가 작을수록 우선순위가 높고, 최대 우선순위 큐는 숫자가 클수록 우선순위가 높습니다.

 

 

최소 우선순위 큐 

var priorityQueue = PriorityQueue<Int>(sort: <)

// 요소 삽입
priorityQueue.enqueue(5)
priorityQueue.enqueue(1)
priorityQueue.enqueue(3)
priorityQueue.enqueue(2)

// 가장 우선순위가 높은 요소(최소값) 확인
print(priorityQueue.peek!) // 1

// 요소 제거
print(priorityQueue.dequeue()!) // 1
print(priorityQueue.dequeue()!) // 2
print(priorityQueue.dequeue()!) // 3
print(priorityQueue.dequeue()!) // 5

 

최대 우선순위 큐

var maxPriorityQueue = PriorityQueue<Int>(sort: >)

maxPriorityQueue.enqueue(5)
maxPriorityQueue.enqueue(1)
maxPriorityQueue.enqueue(3)
maxPriorityQueue.enqueue(2)

// 가장 우선순위가 높은 요소(최대값) 확인
print(maxPriorityQueue.peek!) // 5

// 요소 제거
print(maxPriorityQueue.dequeue()!) // 5
print(maxPriorityQueue.dequeue()!) // 3
print(maxPriorityQueue.dequeue()!) // 2
print(maxPriorityQueue.dequeue()!) // 1

 

 

PriorityQueue는 내부적으로 Heap을 사용하여 효율적으로 요소를 삽입(enqueue)하고 제거(dequeue)합니다.

sort 매개변수에 따라 최소 우선순위 큐로 동작할 수도 있고, 최대 우선순위 큐로 동작할 수도 있습니다.

시간 복잡도는 enqueue와 dequeue 모두 O(log n)입니다.