[Data Structure] Priority Queue 우선순위 큐

우선순위 큐는

힙구조로 이뤄져있죠

 

힙구조란

완전이진트리이고

정렬기준에맞춰서 최댓값이나 최솟값을 빠르게 찾아낼 수 있어요

 

 

새로운 노드를 넣을땐 제일 끝에서 추가해서 

자신의 부모의 인덱스인 (index-1)/2와 비교해서 거꾸로 올라오면서 조건에 맞는지 비교하며

교체가 일어나구요

(logn)

 

삭제할 때는 제일 위부터 아래로 가면서 다시 정렬하면서 교체하는 과정이 일어나요

(logn)

struct PriorityQueue<T> {
    var heap: [T] = []
    let ordered: (T, T) -> Bool
    
    init(ordered: @escaping (T, T) -> Bool) {
        self.ordered = ordered
    }
    
    /// 큐 뒤에 요소 추가
    mutating func enQueue(_ element: T) {
        heap.append(element)
        upHeapify(heap.count - 1)

    }
    
    /// 큐 앞요소 반환후 삭제
    mutating func deQueue() -> T? {
        if heap.isEmpty {
            return nil
        }
        if heap.count == 1 {
            return heap.removeFirst()
        }
        
        heap.swapAt(0, heap.count - 1)
        let temp = heap.removeLast()
        downHeapify(0)
        return temp
    }
    
    /// front에 위치한 요소
    func peek() -> T? {
        return heap.first
    }
    
    var isEmpty: Bool {
        heap.isEmpty
    }
    
    /// 아래에서 위로 비교
    /// 요소를 추가할때 현재 노드의 부모와 비교해서 위로 올라오는 방식을 취함
    private mutating func upHeapify(_ index: Int) {
        var index = index
        
        // 힙의 index위치의 요소와 부모요소를 비교
        while index > 0 && !ordered(heap[(index-1)/2], heap[index]) {
            heap.swapAt((index-1)/2, index)
            index = (index-1)/2
        }
    }
    
    /// 위에서 아래로 비교
    /// 재정렬할때 부모부터 아래로 내려가면서 검사함
    private mutating func downHeapify(_ index: Int) {
        var index = index
        
        while 2 * index + 1 < heap.count {
            var child = 2 * index + 1
            if child < heap.count - 1 && !ordered(heap[child], heap[child+1]) {
                child += 1
            }
            if !ordered(heap[index], heap[child]) {
                heap.swapAt(index, child)
                index = child
            } else {
                break
            }
        }
    }
    
    func printElement() {
        heap.forEach { print($0) }
    }
}