힙을 이용한 우선순위 큐(Priority Queue By Heap)

1. 문제

• 힙을 이용하여 우선순위 큐를 구현

2. 입출력

• 힙을 구현할 배열의 크기를 입력 받음(완전이진트리 이기 때문에 배열로 구현할 수 있음)

3. 문제 설계

• 힙의 경우 완전이진트리 이기 때문에, 배열로 구현할 수 있음
• 완전이진트리는 자식 노드가 2개 이하, 왼쪽부터 값이 차례대로 채워나가는 트리를 말함
• 삽입 연산의 경우 배열의 가장 끝에 원소를 추가하고, 우선순위를 비교하여 트리를 재구성함(문제에서는 최솟값이 우선순위가 높음) 트리의 높이는 노드가 N개일 때, 대략 log N 이므로, 최악의 경우(가장 우선순위가 높은 값이 삽입 됐을 경우, 문제에서는 최솟값) 루트노드 까지 비교해야 하므로 O(log N)의 시간복잡도를 가짐
• 삭제 연산의 경우 우선순위가 가장 높은 루트 노드를 제거하고 가장 끝 단말 노드를 부모 노드에 위치 시키고 최악의 경우 가장 단말 노드 까지 내려가야 하므로 트리의 높이인 log N 만큼 내려갈 수 있음. 따라서 O(log N)의 시간복잡도를 가짐
• 탐색 연산의 경우 우선순위가 가장 높은 루트 노드를 반환하면 되므로, O(1)의 시간복잡도를 가짐
• 배열로 우선순위 큐를 구현했을 때와 비교하게 되면, 삽입 연산의 경우 O(1)과 O(log N)으로 차이가 나지만 삭제 연산의 경우 O(N)과 O(log N)의 차이가 더 크기 때문에, 힙으로 우선순위 큐를 구현하는 것이 바람직함

4. 전체 코드

//MARK: - 우선순위 큐(힙)

//MARK: - Framework
import Foundation

//MARK: - Type
struct PriorityQueue {
    //MARK: - Property
    var data: [Int]
    var len, capacity: Int
    
    //MARK: - Initializer
    init(_ capacity: Int) {
        self.capacity = capacity
        self.data = Array(repeating: 0, count: self.capacity + 10)
        self.len = 1
    }
    
    //MARK: - Method
    mutating func push(_ x: Int) -> Void {
        self.data[self.len] = x
        self.len += 1
        
        var currentIndex: Int = self.len - 1
        while currentIndex > 1 {
            if self.data[currentIndex] < self.data[currentIndex >> 1] {
                let temp: Int = self.data[currentIndex]
                self.data[currentIndex] = self.data[currentIndex >> 1]
                self.data[currentIndex >> 1] = temp
                
                currentIndex >>= 1
            } else {
                break
            }
        }
    }
    
    mutating func pop() -> Void {
        self.data[1] = self.data[self.len - 1]
        self.data[self.len - 1] = 0
        self.len -= 1
        
        var currentIndex: Int = 1
        while true {
            var childIndex: Int = -1
            
            if self.len - 1 < (currentIndex << 1) {
                break
            } else if (0 < (currentIndex << 1) && (currentIndex << 1) <= self.len - 1) && (currentIndex << 1 + 1) > self.len - 1 {
                childIndex = currentIndex << 1
            } else {
                childIndex = (currentIndex << 1) < (currentIndex << 1 + 1) ? (currentIndex << 1) : (currentIndex << 1 + 1)
            }
            
            if self.data[currentIndex] > self.data[childIndex] {
                let temp: Int = self.data[currentIndex]
                self.data[currentIndex] = self.data[childIndex]
                self.data[childIndex] = temp
                
                currentIndex = childIndex
            } else {
                break
            }
        }
    }
    
    func top() -> Int {
        return self.data[1]
    }
}

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let n: Int = Int(readLine() ?? "0") else { return }
    var pq: PriorityQueue = PriorityQueue(n)
    
    //MARK: - Process & Output
    pq.push(5)
    pq.push(8)
    pq.push(1)
    pq.push(3)
    pq.push(3)
    
    print(pq.top()) // 1
    pq.pop()
    
    print(pq.top()) // 3
    pq.pop()
    
    print(pq.top()) // 3
    pq.pop()
    
    print(pq.top()) // 5
    pq.pop()
    
    print(pq.top()) // 8
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.