PriorityQueue (우선순위 큐)

Priority Queue (우선순위 큐)는 말 그대로 사용자가 지정한 조건에 따라 우선순위가 정해집니다. 일반적인 Queue는 단지 데이터가 들어오는 순서에 따라 FIFO(First In First Out) 구조를 따르게 되는데, Priority Queue는 우선순위가 높은 데이터부터 pop됩니다. PriorityQueue는 우선순위에 따라 Heap(힙) 자료구조로 데이터를 저장하게 되기 때문에 삽입과 삭제의 시간복잡도는 O(log n)으로 매우 빠른 시간을 자랑합니다.

 

제가 이 Priority Queue (우선순위 큐)를 Swift로 직접 구현하기 위해 이전 게시물에서 Heap(힙) 자료구조를 공부했었습니다!! Queue도.. Stack도.. PriorityQueue도 없는 Swift는... 사용하려면 귀찮더라도 직접 구현해야하는 것 같더라구요..😂 하지만 swift는 removeFirst, removeLast, insert, append 등등의 메서드를 사용해서 Queue나 Stack같은 기능은 기본배열로도 간단하게 사용할 수 있습니다. 하지만 PriorityQueue는 직접 구현해야하는 것 같아요ㅜㅜ 윽.. 귀찮지만.... 내가 이래서 Java를 아직 버릴 수 없지만..... 그래도 Swift로 Priority Queue를 직접 구현해보았습니다❗️❗️

 

이건 게시물 작성하고 나서 나중에 알게된 사실인데 swift에서는 .sorted(by: { $0.value < $1.value }) 이런식으로 커스텀하게 정렬을 할 수 있었더랍니다ㅎㅎㅎ

 

자세한 동작방식을 보고 싶다면 힙(Heap) 자료구조 이전 게시물을 보고 와주세요!

PriorityQueue 구현 자체가 이전 게시물에서 다룬 Heap 자료구조 구현 코드랑 거의 똑같지만, 이번에 PriorityQueue를 구현하면서 pop할 때 왼쪽 오른쪽 자식노드가 없을 경우까지 고려하였습니다. 제가 직접 구현한 코드라서 다른 분들이 구현한 PriorityQueue와 다를 수 있어요. 혹시 보다가 궁금한 점 있으시면 댓글로 물어봐주세요!

 

---

 

<사용예시>

 

<Swift 구현코드>

class PriorityQueue<T> {
    private var heap: [T] = []
    private let comparing: (_ o1: T,_ o2: T) -> Bool
    
    init(_ comparing: @escaping (_ o1: T,_ o2: T) -> Bool) {
        self.comparing = comparing
    }
    
    func size() -> Int { heap.count }
    
    func isEmpty() -> Bool { heap.isEmpty }
    
    func clear() { heap.removeAll() }
    
    func peek() -> T? { heap.first }
    
    func push(_ value: T) {
        heap.append(value)
        if heap.count == 1 { return }
        var valueIndex = heap.count - 1
        var parentIndex = (valueIndex-1) / 2
        while !comparing(heap[parentIndex], heap[valueIndex]) {
            heap.swapAt(valueIndex, parentIndex)
            valueIndex = parentIndex
            parentIndex = (valueIndex-1) / 2
            if valueIndex == 0 { break }
        }
    }
    
    func pop() -> T? {
        if heap.count == 0 { return nil }
        if heap.count == 1 { return heap.removeFirst() }
        
        func isChildEmpty(_ value: Int,_ left: Int,_ right: Int) -> Bool {
            if heap.count <= left { return true }
            if heap.count > right { return false }
            if comparing(heap[value], heap[left]) { return true }
            heap.swapAt(value, left)
            return true
        }
        
        heap.swapAt(0, heap.count-1)
        let answer = heap.removeLast()
        
        var valueIndex = 0
        var leftIndex = valueIndex * 2 + 1
        var rightIndex = valueIndex * 2 + 2
        
        if isChildEmpty(valueIndex, leftIndex, rightIndex) { return answer }
        
        while !comparing(heap[valueIndex], heap[leftIndex]) || !comparing(heap[valueIndex], heap[rightIndex]) {
            let index = comparing(heap[leftIndex], heap[rightIndex]) ? leftIndex : rightIndex
            heap.swapAt(valueIndex, index)
            valueIndex = index
            leftIndex = valueIndex * 2 + 1
            rightIndex = valueIndex * 2 + 2
            
            if isChildEmpty(valueIndex, leftIndex, rightIndex) { break }
        }
        return answer
    }
}