자료구조 | 힙(Heap), 우선순위 큐(Priority Queue)

우선순위 큐는 대표적으로 다익스트라 알고리즘에서 사용된다. (또 A* 알고리즘, 허프만 코딩 알고리즘 등에서도 쓰인다고 한다)

큐, 데큐가 선형 자료구조인 것과 달리, 우선순위 큐는 주로 힙(Heap)으로 구현되는 경우가 많기 때문에 비선형으로 분류된다. 

 

우선순위 큐를 구현하는데 필요한 힙(Heap)이라는 자료구조가 무엇인지 알아보고, 우선순위 큐에 대해서 알아보자.

---

힙(Heap)

Heap은 완전 이진 트리의 일종으로, 1) 최소 힙 또는 2) 최대 힙으로 나뉜다.

힙 속성(Heap Property)

• 최소 힙(Min-Heap): 각 노드의 값이 그 자식 노드의 값보다 작거나 같음 (루트 노드가 최소값)
• 최대 힙(Max-Heap): 각 노드의 값이 그 자식 노드의 값보다 크거나 같음 (루트 노드가 최대값)

 

특성

구조적 특성

• Heap은 완전 이진 트리의 구조를 가진 덕에 배열을 사용해서 표현될 수 있으며, n개의 인덱스에 대해 힙의 높이는 log(n)가 된다. 
• 완전 이진 트리이므로 부모 노드의 인덱스를  i 라고 하면, 언제나 left child의 인덱스는 2*i+1 , right child의 인덱스는  2*i+2 이다. 
• 반대로 자식 노드의 인덱스를  j  라고 하면, 언제나 부모 노드의 인덱스는  (j-1)/2 의 반내림 이다.

 

정렬된 특성

• 위에서 언급된 힙 속성을 항상 유지하는 덕분에, 루트 노드에 접근하면 최대값과 최소값을 바로 얻을 수 있다. 즉, 언제나 최대값과 최소값을 O(1)의 시간 복잡도로 얻을 수 있다. 
• 삽입, 삭제 연산도 항상 이를 유지하면서 수행된다. 그 과정에서 O(log n)이 소요된다.
• 검색 연산의 경우, 최대값/최소값은 O(1) 그 외의 임의의 요소는 O(n)이 소요된다. 

 

이러한 특성 덕에 Heap은 주로 1) 스케줄링과 관련된 알고리즘을 짤 때나, 위에서 언급하였듯 우선순위 큐를 구현할 때 사용된다.

 

파이썬에서의 구현

파이썬에서 힙은  import heapq 를 통해 구현할 수 있다.

import heapq

#------ 최소 힙 ------#
min_heap = []

# 삽입
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 7)
print(min_heap)  # 결과: [3, 5, 7]

# 최소값 검색
min_value = min_heap[0]  # 루트 노드 조회
print(min_value)  # 결과: 3

# 삭제
min_value = heapq.heappop(min_heap)  # 루트 노드(최소값) 삭제 및 반환
print(min_value)  # 결과: 3
print(min_heap)  # 결과: [5, 7]




#------ 최대 힙 ------#
max_heap = []

# 삽입
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)
print([-i for i in max_heap])  # 결과: [7, 3, 5]

# 최대값 검색
max_value = -max_heap[0]  # 루트 노드 조회
print(max_value)  # 결과: 7

# 삭제
max_value = -heapq.heappop(max_heap)  # 루트 노드(최대값) 삭제 및 반환
print(max_value)  # 결과: 7
print([-i for i in max_heap])  # 결과: [5, 3]

 

파이썬의 heapq 모듈은 기본적으로 최소 힙만을 지원한다. 따라서 최대 힙을 구현할 때는 음수 부호(-)를 붙여 음수로 넣는 트릭을 쓴다.

이렇게 하면 최소 힙의 규칙에 따라 정렬되어도 - 부호만 빼고 보면 최대 힙의 특성을 지니게 된다. 

이를 다시 꺼낼 때는 다시 - 부호를 붙여 양수로 출력되도록 한다. 

 

---

참고로, heapq에서 특정 값을 뺀 후에 다시 출력해보면, 나는 삭제만 했을 뿐인데 배열 구조가 바뀌어 있음을 확인할 수 있다.

이는 연산이 이루어질 때마다 내부적으로 힙 특성을 유지하기 위해 정렬을 자동으로 수행하기 때문이다.

'''
heapq 모듈은 리스트의 첫 번째 요소(인덱스 0)가 항상 힙의 최소값을 가지도록 유지한다. 
그러나 나머지 요소들은 특정 순서로 정렬되지 않는다. 대신 이들 요소는 힙 속성을 유지하기 위해 정렬된다.  
'''

import heapq

heap = []
for i in range(10):
    heapq.heappush(heap, i)
print(heap) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in range(3):
    a = heapq.heappop(heap)
    print(a)
print(heap) # [3, 4, 5, 7, 9, 8, 6]

heapq.heappushpop(heap, 99) # pop과 동시에 새로운 요소 push
print(heap) # [4, 7, 5, 99, 9, 8, 6]

---

 

heapq는 내부적으로 어떻게 동작할까?

위 예시에서 본 삽입, 삭제, 검색은 heapq 모듈의 메서드를 활용한 방법이다. 힙의 특성을 유지하기 위한 정렬 등의 연산을 heapq 모듈이 내부적으로 수행한다. heapq 자료구조가 제공하는 정렬 등의 특성이 아무 비용없이 이루어지는 건 아닌 것이다. (즉, 모듈 내부적으로 시간복잡도를 소요한다.)

 

그럼 우리가 heappush(), heappop() 등 연산을 수행하면, heapq 내부에서는 어떤식으로 이를 구현할까?

이를 이해해야 시간 복잡도에 대한 이해도 생기고, 또 나중에 자료구조 자체를 요구사항에 맞게 최적화해야 하는 경우 직접 구현할 수도 있을 것이다. 

 

따라서 heapq의 동작 과정을 파이썬으로 구현해보기로 했당

 

 

1. 삽입 연산

 

배열의 마지막에 요소를 추가한 후, 이 요소가 힙 속성을 만족할 때까지 부모 노드와 위치를 바꾼다.

이를 'heapify up'이라고 한다.

# heap 배열 정의
heap = []

# 삽입 연산
def insert(heap, value):
    # Heapify up
    heap.append(value)  # 요소를 배열의 마지막에 삽입
    index = len(heap) - 1  # 새로 삽입된 요소의 인덱스 배정
    while index > 0:  # 루트 노드에 도달할 때까지 또는 힙 속성이 유지될 때까지 반복
        parent_index = (index - 1) // 2  # 부모 노드의 인덱스 계산
        if heap[index] < heap[parent_index]:  # 최소 힙의 경우, 새 노드가 부모 노드보다 작으면
            heap[index], heap[parent_index] = heap[parent_index], heap[index]  # 새 노드와 부모 노드의 위치를 바꿈
            index = parent_index  # 새 노드의 인덱스를 부모 노드의 인덱스로 업데이트
        else:
            break  # 힙 속성이 유지되면 종료

 

2. 삭제 연산

 

루트 노드를 삭제할 때는, 배열의 마지막 요소를 루트 노드로 이동한 후, 이 노드가 힙 속성을 만족할 때까지 자식 노드와 위치를 바꾼다.

이를 "heapify down"이라고 한다.

# 삭제 연산
def delete(heap):
    if not heap:
        return None  # 힙이 비어있으면 None 반환
    root = heap[0]  # 루트 노드의 값 저장
    heap[0] = heap.pop()  # 배열의 마지막 요소를 루트로 이동
    index = 0
    while index * 2 + 1 < len(heap):  # 왼쪽 자식 노드가 존재하는 동안 반복
        child_index = index * 2 + 1  # 왼쪽 자식 노드의 인덱스 계산
        # 오른쪽 자식 노드와 비교 (최소 힙의 경우)
        if child_index + 1 < len(heap) and heap[child_index] > heap[child_index + 1]:
            child_index += 1  # 오른쪽 자식 노드가 더 작으면 오른쪽 자식 노드를 선택
        if heap[index] > heap[child_index]:  # 현재 노드가 선택된 자식 노드보다 크면
            heap[index], heap[child_index] = heap[child_index], heap[index]  # 현재 노드와 자식 노드의 위치를 바꿈
            index = child_index  # 현재 노드의 인덱스를 자식 노드의 인덱스로 업데이트
        else:
            break  # 힙 속성이 유지되면 종료
    return root  # 삭제된 루트 노드의 값 반환

 

3. 검색(조회) 연산

 

루트 노드의 값을 조회하려면 배열의 첫 번째 요소를 반환하면 된다.

# 검색(조회) 연산
def peek(heap):
    return heap[0] if heap else None  # 힙이 비어있지 않으면 루트 노드의 값 반환, 비어있으면 None 반환

 

시간 복잡도

위 절차에 따르면 heapq의 각 연산에 소요되는 시간복잡도는 다음과 같다.

연산	시간 복잡도
Insert	O(log n)
Delete	O(log n)
Peek	O(1) (임의의 값 검색인 경우 O(n))

 

 

우선순위 큐(Priority Queue)

우선순위 큐는 큐의 변형된 형태이다. 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 특성을 지닌다. 

 

이 특성을 우선순위에 적용하면 다양한 응용이 가능하다. 

 

우선순위 큐에선 가장 먼저 들어온 데이터가 먼저 나가는 것이 아니라, 우선순위가 가장 높은 요소가 먼저 나간다. 해당 자료구조는 데이터의 삽입, 삭제 연산을 지원한다. 

 

힙(Heap)과 우선순위 큐(Priority Queue) 비교

	Heap	Priority Queue
정의	데이터의 부분 순서를 유지하는 이진 트리 기반의 데이터 구조	각 요소가 우선순위를 가지며, 우선순위에 따라 요소를 처리하는 추상 데이터 타입
구현	배열을 사용하여 구현	Heap 또는 다른 데이터 구조를 사용하여 구현
주요 연산	삽입, 삭제, 최소(또는 최대)값 조회	삽입, 삭제
우선순위 처리	최소 힙은 최소값, 최대 힙은 최대값을 루트 노드에 유지	높은 우선순위의 요소를 먼저 처리
효율성	삽입 및 삭제 연산의 시간 복잡도는 O(log n)	Heap을 사용하면 삽입 및 삭제 연산의 시간 복잡도는 O(log n)
적용 예	Priority Queue 구현, 그래프 알고리즘(예: Dijkstra’s Algorithm), 스케줄링 등	스케줄링, 네트워크 트래픽 제어, 시뮬레이션, 데이터 압축 등

 

우선순위 큐 구현

우선순위 큐는 힙으로 주로 구현된다. 힙의 구조와 연산이 우선순위 큐의 요구 사항을 충족시키기 때문이다.

• 최소 힙은 최소 우선순위 요소를 먼저 처리하는 우선순위 큐를 구현하는 데 사용할 수 있다.
  • 최소 우선순위 요소가 삭제되면, 그 다음으로 작은 값이 최소 우선순위 요소로 내려온다. 
• 최대 힙은 최대 우선순위 요소를 먼저 처리하는 우선순위 큐를 구현하는 데 사용할 수 있다. 
  • 최대 우선순위 요소가 삭제되면, 그 다음으로 큰 값이 최대 우선순위 요소로 올라온다.

힙의 노드 간의 값의 크기로 우선순위 큐의 우선순위를 표현하는 것이다. 

 

파이썬에서 이를 구현할 때는 두 가지 방향이 있다. 1) heapq 모듈 사용, 2) queue 모듈의 PriorityQueue 클래스 사용

PriorityQueue 클래스는 우선순위 큐를 다룸에 있어서 더 직관적인(=high level) 인터페이스를 갖고 있다. 

때문에 코드를 짜는 입장에서 더욱 편하다는 장점이 있다. 그러나 해당 클래스도 내부적으로는 heapq 모듈로 구현되어 있다. 

 

반대로 heapq는 low level 인터페이스를 갖고 있으므로, PriorityQueue 클래스 대비 특정 조건이나 요구 사항에 맞게 다룰 수 있다. 

만일 실제 서비스에서 단순히 모듈을 사용하는 수준 이상의 최적화가 필요하다면, 위에서 쓴 heapq 내부 동작을 살짝 바꿔서 직접 구현해야 할 것이다. 

 

그래서 애초에 heapq 모듈 사용법에 익숙해지는 게 나을 것 같다.

import heapq

# 우선순위 큐를 빈 배열로 초기화
priority_queue = []

# 삽입 연산: 우선순위와 항목을 튜플로 묶어서 삽입
heapq.heappush(priority_queue, (우선순위, 넣을 항목)) # 이때, 낮은 숫자가 높은 우선순위를 나타낸다
# 예시: heappush(priority_queue, (1, 'item1')) 

# 삭제 연산: 최소 우선순위 항목을 삭제하고 반환
priority, item = heapq.heappop(priority_queue)

# 최소 우선순위 항목 조회: 리스트의 첫 번째 항목이 최소 우선순위 항목
priority, item = priority_queue[0]

# 우선순위 큐의 모든 항목을 정렬된 순서로 반환
# heapq.nsmallest() 함수를 사용하면 우선순위 큐의 모든 항목을 정렬된 순서로 반환할 수 있다.
sorted_items = [item for priority, item in heapq.nsmallest(len(priority_queue), priority_queue)]

 

 

위와 같이 heapq 와 같은 문법이다. 그러나 접근하는 사고방식만 우선순위 큐에 맞게 조금 바꾸면 된다.