[WEEK02] 우선순위 큐

우선순위 큐

우선순위 큐

우선순위 큐는 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.

우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다. 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다.

• 하나의 원소를 우선순위를 지정하여 추가하는 함수(push)
• 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환하는 함수(pop)

힙(Heap)

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다.

최소 heap 구현

import heapq

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

# 출력 결과 [0,1,2,3,4,5,6,7,8,9]

최대 heap 구현

# 파이썬은 최대 힙을 제공하지 않으므로 아래와 같이 부호를
# 변경하는 방식으로 최대 힙을 사용한다.
import heapq

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

# 출력 결과 [9,8,7,6,5,4,3,2,1,0]

우선순위 큐 관련 백준 문제 Github 링크
백준 우선순위 큐 관련 문제