우선순위 큐 Priority Queues

우선순위 큐(Priority queue)

1. 정의: 각 요소에 우선순위가 할당된 큐

2. 특징:
   - 높은 우선순위 요소가 먼저 처리됨
   - 동적으로 요소 추가/제거 가능

3. 주요 연산:
   - 삽입: 새 요소 추가
   - 최대값 추출: 최고 우선순위 요소 제거 및 반환
   - 우선순위 변경: 요소의 우선순위 수정

우선순위 기반 데이터 관리에 효과적이고 주로 큐로 구현합니다.

 

---

우선순위 큐 특징

 

1. 동적 집합 S를 유지합니다. 이는 요소들이 추가되거나 제거될 수 있음을 의미합니다.

초기 상태:
S = { }  (빈 집합)

요소 추가 후:
S = { 5, 3, 8 }

또 다른 요소 추가:
S = { 5, 3, 8, 1 }

요소 제거 후:
S = { 5, 8, 1 }

2. 각 집합의 요소는 키(key)라고 하는 연관된 값을 가집니다. 이 키는 요소의 우선순위를 결정합니다.

요소1: (데이터: "작업A", 키: 5)
요소2: (데이터: "작업B", 키: 3)
요소3: (데이터: "작업C", 키: 8)

요소3이 가장 우선순위(8)가 높으니 먼저 처리됩니다.

3. 최대 우선순위 큐는 다음과 같은 동적 집합 연산을 지원합니다:

   a. INSERT(S, x): 요소 x를 집합 S에 삽입합니다.
   
   b. MAXIMUM(S): S에서 가장 큰 키를 가진 요소를 반환합니다.
   
   c. EXTRACT-MAX(S): S에서 가장 큰 키를 가진 요소를 제거하고 반환합니다.
   
   d. INCREASE-KEY(S, x, k): 요소 x의 키 값을 k로 증가시킵니다. 단, k는 x의 현재 키 값보다 크거나 같아야 합니다.

이러한 연산들을 통해 우선순위 큐는 항상 가장 높은 우선순위(여기서는 가장 큰 키 값)를 가진 요소에 빠르게 접근하고 조작할 수 있습니다. 이는 다양한 알고리즘과 응용 프로그램에서 유용하게 사용됩니다.

우선순위 큐는 주로 힙(Heap) 자료구조를 사용하여 구현되며, 이를 통해 효율적인 연산이 가능합니다.

힙에대해서 모르겠다면 아래 포스트를 참고해주시기 바랍니다.

https://kimyir.tistory.com/106

힙, 힙 정렬이란 Heap, Heap Sort

 

---

힙으로 구현

 

HEAP-EXTRACT-MAX(S)

 

이제 우선 순위 큐의 힙 의사 코드를 봅시다.

단계적 설명

아까 EXTRACT-MAX(S)뜻이 "S에서 가장 큰 키를 가진 요소를 제거하고 반환합니다." 라고 했는데

코드를 보면 heap-size[A] 배열이 비어있지 않다면 루트 노드에 있는 최대값 A[1]을 저장해줍니다.

그리고 A[1]을 A[heap-size]번째, 즉 마지막 노드로 이동한 뒤, 힙 크기를 감소합니다.

이렇게 가장 우선순위(최대값) 노드를 얻었으면 MAX-HEAPIFY 작업을 하여 다시 최대힙으로 정렬해줍니다.

 

특징:

• 최대값 추출 후 힙 구조 유지
• 시간 복잡도: O(log n) (MAX-HEAPIFY 때문)

활용:

• 우선순위 큐 구현
• 힙 정렬 알고리즘의 일부

def heap_extract_max(A):
    if len(A) - 1 < 1:  # heap-size[A] < 1
        raise ValueError("힙 언더플로우")
    
    max_val = A[1]  # max ← A[1]
    A[1] = A[len(A) - 1]  # A[1] ← A[heap-size[A]]
    A[len(A) - 1] = None  # 마지막 요소를 None으로 설정
    A.heap_size -= 1  # heap-size[A] ← heap-size[A] - 1
    
    max_heapify(A, 1)  # MAX-HEAPIFY(A, 1)
    
    return max_val
    
# 사용 예
heap = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
print("원래 힙:", heap)
max_val = heap_extract_max(heap)

실제 예시 파이썬 코드입니다.

 

 

 

HEAP-INCREASE-KEY(A,i,key)

 

그 다음은 위에서 얘기한 INCREASE-KEY(S, x, k)의 의사코드입니다.

이 함수는 요소 x의 키 값을 k로 증가시킵니다.

단, k는 x의 현재 키 값보다 크거나 같아야 합니다. 최대 힙 속성을 유지 해야하기 때문입니다.

 

매개변수:

   - A: 힙 배열
   - i: 키를 증가시킬 노드의 인덱스
   - key: 새로운 키 값

 

단계별 설명:

   1) 새 키가 현재 키보다 작은지 확인
   2) 노드의 키 값을 새 값으로 업데이트
   3) 부모 노드와 비교하며 필요시 교환 (상향 이동)

 

값이 바뀌기 때문에 우선순위 큐에서 요소의 우선순위 변경할 수 있습니다.
또한 다익스트라 알고리즘 등에서 사용되는걸로 압니다.

 

MAX-HEAP-INSERT(A, key)

 

MAX-HEAP-INSERT(A, key), 위에서도 있었는데

INSERT(S, x) : 요소 x를 집합 S에 삽입합니다.

그럼 각각 S와 x를 A와 key로 대입하면 

   - A: 힙 배열
   - key: 삽입할 새로운 키 값
가 되겠습니다.

단계별 설명: 

   1) 힙 크기를 1 증가시킵니다.
   2) 새 노드를 힙의 마지막에 -∞ 값으로 추가합니다.
   3) HEAP-INCREASE-KEY 함수를 호출하여 새 노드의 키 값을 설정하고 적절한 위치로 이동시킵니다.

 

주요 특징:

   - 새 요소를 힙의 마지막에 추가한 후 상향식으로 조정
   - 시간 복잡도: O(log n) (HEAP-INCREASE-KEY의 복잡도와 동일)

 

활용:

   - 우선순위 큐에 새로운 요소 추가
   - 힙 정렬 알고리즘의 일부로 사용

MAX-HEAP-INSERT(A, 키)