[알고리즘] 우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐(Prioriy Queue)

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

큐의 동작 방식은 기본적으로 선입선출이다.
하지만 우선순위 큐는 우선순위가 가장 높은 데이터가 먼저 삭제된다.
ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우

우선순위 큐를 구현하는 방법

1. 리스트를 기반으로 구현
2. 연결 리스트를 기반으로 구현
3. 힙을 이용하여 구현

리스트와 연결리스트의 경우 구현 방법은 쉽다. 하지만 치명적인 단점이 존재한다.

리스트의 경우 data가 많아 질 경우 데이터를 우선순위에 기반해 전체 비교를 거쳐 알맞은 자리를 찾고,
그 자리에 넣기 위해 전체 자료를 밀어내야한다.

연결리스트의 경우 또한 data가 많아 질 경우 노드간의 연결을 거쳐 모든 노드에 접근하여 비교연산을 해야한다.
이는 비용이 매우 크다.

따라서 우리는 힙을 이용해 우선순위 큐를 구현한다.

힙(Heap)

힙은 완전 이진 트리 자료구조의 일종이다. 우선순위 큐를 위해 고안되었다.

힙의 종류

최대 힙

루트 노드가 가장 큰 값을 가진다. 따라서 값이 가장 큰 데이터가 우선적으로 제거된다.

최소 힙

루트 노드가 가장 작은 값을 가진다. 따라서 값이 가장 작은 데이터가 우선적으로 제거된다.

힙의 삽입

힙에서 삽입이 발생할 경우 다음과 같이 힙의 조건을 만족하지 않는 경우가 발생할 수 있다.
따라서 위와 같이 최소 힙 성질을 만족하기 위해 부모 노드와 교체하는 방식으로 재구성 한다.

시간 복잡도

다음과 같이 노드가 6개이지만 2번의 연산만으로 힙 성질을 유지할 수 있다.
따라서 O(logN)의 시간 복잡도를 가진다.

힙의 삭제

힙의 삭제의 경우 루트 노드자리에 가장 마지막 노드를 대체시킨다.
그리고 다음과 같이 힘 성질을 만족하기위한 연산을 수행한다.

힙 사용

#우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제(Python)
import heapq

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

    return result


arr = [3, 2, 5, 4, 7, 1]

res = heapsort(arr)

print(res)

[1, 2, 3, 4, 5, 7]

파이썬은 기본적으로 최소 힙 라이브러리를 제공한다.

최대 힙

그렇다면 파이썬에서 최대 힙을 사용하려면 어떻게 해야할까?

#우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제(Python)
import heapq

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

    return result


arr = [3, 2, 5, 4, 7, 1]

res = heapsort(arr)

print(res)

[7, 5, 4, 3, 2, 1]

약간의 요령이 필요하다.
위와 같이 heap에 하나의 원소만 넣지 말고, 가짜 우선순위와 실제 우선순위를 넣는다.

7의 경우 가짜는 -7, 실제는 7이다. 따라서 heappush에서 가짜 우선순위를 기준으로 최소 힙이 구성된다.

[(-7, 7), (-5, 5), (-3, 3), (-2, 2), (-4, 4), (-1, 1)]

그리고 꺼낼 때는 가짜가 아닌 실제 우선순위로 꺼내면 마치 최대 힙을 사용한 것과 같은 결과를 얻을 수 있다.