[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)

# 우선순위 큐 (Priority Queue)

 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트(List), 힙(Heap) 두가지 방식으로 구현 가능하다.

 리스트의 경우 데이터를 단순히 리스트의 뒤에 삽입하고 우선순위를 기준으로 선형탐색한다. 따라서 삽입시간은 시간복잡도가 O(1)이지만, 삭제시간은 선형탐색으로 인해 O(N)이 소요된다.

 반면, 힙은 삽입시간, 삭제시간 모두 O(logN)의 시간복잡도를 보장한다. 힙의 또다른 특징은 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다는 점이다. 이를 힙 정렬(Heap Sort)이라 하는데, 힙 정렬은 O(NlogN)의 시간 복잡도를 가진다.

 

# 힙 (Heap)

 힙은 완전 이진 트리 자료구조의 일종으로 데이터 삭제시 항상 루트 노드(root node)를 제거한다. 힙은 최소 힙(min heap)과 최대 힙(max heap) 두 가지로 분류된다. 최소 힙은 루트 노드가 가장 작은 값을 가지며 값이 작은 데이터가 우선적으로 제거된다. 오름차순 정렬을 수행하고 싶다면, 최소 힙에 데이터를 넣고 꺼내기만 하면 된다. 반면에 최대 힙은 루트 노드가 가장 큰 값을 가지며 값이 큰 데이터가 우선적으로 제거된다. 최대 힙에 데이터를 넣고 꺼내는 방식으로 내림차순 정렬 수행이 가능하다.

 최소 힙을 예시로 구현 방식을 살펴보자. 힙 자료구조가 힙의 성질을 갖게하기 위해 힙 구성함수 Heapify()를 사용할 수 있다. 최소 힙에 사용되는 최소 힙 구성함수 Min-Heapify()는 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.(상향식)

 위와 같이 힙에 새로운 원소가 삽입될 때, 삽입된 원소는 자신보다 더 작은 값이 있다면 위치를 교체하며 부모 노드 방향으로 거슬러 올라간다. 이러한 방식은 O(logN)의 시간 복잡도를 보장하며 힙의 성질을 유지하게 한다.

 원소를 제거할 때는 루트 노드 위치에 가장 마지막 노드가 오게 하고, 루트 노드에서 하향식으로 더 작은 자식 노드를 찾아 위치를 바꾸며 Heapify()를 사용한다. 이러한 방식은 마찬가지로 O(logN)의 시간 복잡도를 지닌다.

 

 다음은 파이썬으로 구현한 Heap Sort 소스코드이다. (Min-Heap 방식)

import sys
import heapq
input = sys.stdin.readline


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


n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])

 힙을 구현할 때는 파이썬의 heapq 라이브러리를 사용한다. heapq는 기본적으로 Min-Heap으로 동작하는데, Max-Heap을 구현하고 싶다면 데이터를 삽입할 때와 꺼낼 때 데이터 값에 -(마이너스)를 붙여서 진행한다. 예를 들어, 위의 코드에서는 heapq.heappush(h, -value), result.append(-heapq.heappop(h))으로 수정하면 최대 힙이 동작한다.

 

# 완전 이진 트리 (Complete Binary Tree)

 루트 노드부터 시작해 왼쪽 자식 노드부터 오른쪽 자식 노드 순서로 데이터를 차례대로 삽입하는 트리(tree)를 의미한다.

 

 

본 포스팅은 '안경잡이 개발자' 나동빈 님의 저서

'이것이 코딩테스트다'와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.