우선순위 큐란?

정의

• 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 나가는 자료구조
• 우선순위에 따라 처리 순서가 결정되는 추상 자료형

특징

• 선입선출(FIFO - First In First Out) 구조인 일반 큐와는 달리, 요소의 우선 순위에 따라 처리 순서가 달라진다.

  

  • 4 → 8 → 3 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리순서는 다음과 같다. (높은 값이 높은 우선순위를 갖는다고 가정)
    • input : 4 → 8 → 3
    • 큐 : 4 → 8 → 3
    • 우선순위 큐 : 8 → 4 → 3

• 내부적으로 다양한 자료구조(힙, 연결 리스트, 배열)를 사용하여 구현될 수 있으나 효울성을 위해 주로 힙을 사용한다.

  

  • 배열 기반 구현
    • 삽입은 빠르나 최우선 요소를 찾는 데에는 시간이 많이 걸린다.
  • 연결 리스트 기반 구현
    • 최우선 요소를 쉽게 찾을 수 있으나 삽입과 제거에 더 많은 시간이 소요될 수 있다.
  • 힙 기반 구현
    • 최우선 요소의 삽입과 제거 모두에 효율적이다.
    • 힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙으로 구현한다.

기본 동작

※ 값이 클수록 우선순위가 높다고 가정 (최대 힙)

• peek()

  • 우선순위 큐에서 최대 우선순위 값을 반환한다.
  • 최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환한다.

• enqueue()

  • 우선순위 큐(최대 힙)에 요소를 삽입하는 작업을 한다.
  • 삽입 작업은 다음과 같다.

    1. 힙 끝에 새 요소를 삽입

    2. 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꾼다.

    3. 힙 속성이 유지될 때까지 2번 작업을 반복