우선순위 큐

우선순위 큐는 가장 중요한 엘리먼트가 항상 맨 앞에 위치하는 큐다.

큐는 최대 우선순위 큐(가장 큰 엘리먼트가 먼저) 또는 최소 우선순위 큐(가장 작은 엘리먼트가 먼저)로 구현할 수 있다.

우선순위 큐를 사용하는 이유

우선순위 큐는 많은 수의 항목을 처리해야 하고, 반복적으로 가장 크거나 작은 항목(또는 "가장 중요한" 항목)을 식별해야 하는 알고리즘에 유용하다.

우선순위 큐를 활용할 수 있는 알고리즘 예시는 다음과 같다:

• 이벤트 기반 시뮬레이션. 각 이벤트에 타임스탬프를 부여하고, 타임스탬프 순서대로 이벤트를 실행하려 한다. 우선순위 큐를 사용하면 다음에 시뮬레이션해야 할 이벤트를 쉽게 찾을 수 있다.
• 그래프 탐색을 위한 다익스트라 알고리즘. 최소 비용을 계산하기 위해 우선순위 큐를 사용한다.
• 데이터 압축을 위한 허프만 코딩. 이 알고리즘은 압축 트리를 구축한다. 부모 노드가 없는 가장 작은 빈도를 가진 두 노드를 반복적으로 찾아야 한다.
• 인공지능을 위한 A* 경로 탐색.
• 그 외에도 다양한 분야에서 활용된다.

일반 큐나 평범한 배열을 사용하면 다음으로 큰 항목을 찾기 위해 전체 시퀀스를 반복적으로 스캔해야 한다. 우선순위 큐는 이런 작업에 최적화되어 있다.

우선순위 큐를 활용하는 방법

우선순위 큐에서 자주 사용하는 주요 작업:

• Enqueue: 큐에 새로운 요소를 삽입한다.
• Dequeue: 큐에서 가장 중요한 요소를 제거하고 반환한다.
• Find Minimum 또는 Find Maximum: 가장 중요한 요소를 반환하지만 제거하지는 않는다.
• Change Priority: 알고리즘이 큐에 이미 있는 요소의 중요도를 변경해야 할 때 사용한다.

우선순위 큐 구현 방법

우선순위 큐는 다양한 방식으로 구현할 수 있다:

• 정렬된 배열로 구현할 수 있다. 가장 중요한 항목이 배열의 끝에 위치한다. 단점은 새 항목을 삽입할 때 정렬된 순서로 삽입해야 하기 때문에 속도가 느리다.
• 균형 이진 탐색 트리로 구현할 수 있다. 이 방식은 "최소값 찾기"와 "최대값 찾기"를 모두 효율적으로 수행할 수 있어 양방향 우선순위 큐를 만들기에 적합하다.
• 힙으로 구현할 수 있다. 힙은 우선순위 큐를 위한 자연스러운 자료구조다. 사실, 두 용어는 종종 동의어로 사용된다. 힙은 부분적으로만 정렬되어 있기 때문에 정렬된 배열보다 효율적이다. 모든 힙 연산은 **O(log n)**의 시간 복잡도를 가진다.

다음은 힙을 기반으로 한 Swift 우선순위 큐 예제다:

public struct PriorityQueue<T> {
  fileprivate var heap: Heap<T>

  public init(sort: (T, T) -> Bool) {
    heap = Heap(sort: sort)
  }

  public var isEmpty: Bool {
    return heap.isEmpty
  }

  public var count: Int {
    return heap.count
  }

  public func peek() -> T? {
    return heap.peek()
  }

  public mutating func enqueue(element: T) {
    heap.insert(element)
  }

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

  public mutating func changePriority(index i: Int, value: T) {
    return heap.replace(index: i, value: value)
  }
}

보는 바와 같이, 우선순위 큐를 만드는 것은 간단하다. 힙이 있다면 우선순위 큐를 쉽게 만들 수 있다. 왜냐하면 힙은 기본적으로 우선순위 큐이기 때문이다.

추가 자료

위키피디아: 우선순위 큐

Swift 알고리즘 클럽을 위해 Matthijs Hollemans가 작성