/
/

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

cs자료구조
avatar
유댕이
2025.03.20
·
4 min read

힙 Heap

  • 완전 이진트리의 일종으로, 주로 최댓값과 최솟값을 빠르게 찾기 위해 사용된다.

  • 힙은 가장 높거나 가장 낮은 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징을 가지며, 이를 우선순위 큐에 활용할 수 있다.

    • 최대 힙 (Max Heap) : 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 트리

    • 최소 힙 (Min Heap) : 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 트리

      4187

  • 힙에서의 부모노드와 자식노드의 관계

    • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2

    • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1

    • 부모의 인덱스 = (자식의 인덱스) / 2

우선순위 큐 Priority Queue

4188

  • 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 먼저 나가는 자료구조

  • 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하며, 주로 가장 효율적인 힙(heap)으로 구현한다.

    • 배열과 연결리스트의 시간복잡도는 O(n)이다.

    • 힙의 시간복잡도는 O(log2n)이다.

  • 파이썬에서 heapq 와 PriorityQueue 모듈을 활용하여 구현할 수 있다.

    • heapq 모듈은 완전 이진트리 기반의 최소 힙 자료구조이다. 즉, 루트 노드는 가장 작은 값을 가진다.

    • PriorityQueue는 Thread-Safe 하고, heapq는 Non-Safe 와 같은 차이가 있는데, 전자의 경우는 확인 절차를 거치기 때문에 속도가 더 느리다.

    • 따라서 코딩테스트에서는 시간효율성을 위해 heapq를 사용한다.

(1) 힙 추가 : heappush()

import heapq

heaps = []
heapq.heappush(heaps, 1)
heapq.heappush(heaps, 4)
heapq.heappush(heaps, 3)
heapq.heappush(heaps, 2)
print(heaps) # [1, 2, 3, 4]

(2) 힙 삭제 : heappop()

print(heapq.heappop(heaps)) # 1
print(heaps) # [2, 3, 4]
print(heapq.heappop(heaps)) # 2

(3) 힙 변환 : heapify()

  • 리스트를 즉각적으로 heap으로 변환 (O(n))

import heapq

h_list = [[4, "fourth"], [2, "second"], [3, "third"], [1, "first"]]
heapq.heapify(h_list)
print(h_list) # [[1, 'first'], [2, 'second'], [3, 'third'], [4, 'fourth']]

최대 힙 구현

import heapq

values = [1, 2, 3, 4, 5]
heaps = []
max_heap = []

for value in values:
    heapq.heappush(heap, -value)
print(heaps) # [-5, -4, -3, -2, -1]

for item in heaps:
    max_heap.heappush(max_heap, -item)
print(max_heap) # [5, 4, 3, 2, 1]

Reference

  • 이것이 컴퓨터과학이다

- 컬렉션 아티클