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

우석SONG 2022. 1. 12. 22:37

백준 1715번 문제를 풀다가 "우선 순위 큐(Priority Queue)"에 대해 알게 되었고 우선순위 큐를 구현하기 위해 파이썬의 heapq 모듈 사용 중 heapq.heappush 하는 과정이 이해가 가지 않아서 이를 계기로 '나동빈'님의 영상을 보게 되었습니다.

import heapq #heap 라이브러리 import
heap_list = []
iterable =[3,5,9,6,4]
 
for value in iterable :
  heapq.heappush(heap_list,value) #heap 라이브러리의 heappush 함수를 이용해서 iterable의 원소를 heap_list에 추가
  print(heap_list)

위의 코드는 파이썬에서 heap 라이브러리를 import하고 heapq.heappush 함수를 이용해서

iterable이라는 이름의 list의 원소를 하나씩 heap_list에 추가하는 코드입니다.

코드의 출력으로

[3]

[3, 5]

[3, 5, 9]

[3, 5, 9, 6]

[3, 4, 9, 6, 5]

다음과 같이 나오게 되는데, 결과 5번째 줄에 '원소 4'가 추가 될 때 '원소 5'와 순서가 바뀌는 것을 보고 heap 에 데이터를 추가할 때 따르는 규칙에 대해 궁금하게 되어 '나동빈' 님의 영상을 찾아보게 되었습니다.

이 게시글은 유튜브 '동빈나' 님의 영상(https://www.youtube.com/watch?v=AjFlp951nz0)을 바탕으로 공부한 것을 정리한 내용입니다.

우선 순위 큐(Priority Queue)를 설명하기 앞서 먼저 3가지 자료구조에 대해 알아보도록 하겠습니다.

자료구조 : 추출되는 데이터

- 1. Stack : 가장 나중에 삽입된 데이터부터 추출(LIFO 구조 : Last In First Out)

- 2. Queue : 가장 먼저 삽입된 데이터(FIFO 구조 : First In First Out) ->파이썬에선 보통 'deque' 를 사용해서 구현

- 3. Priority Queue : 가장 우선 순위가 높은 데이터

이 중에서 3. Priority Queue를 구현하는 방법 2가지와 시간 복잡도에 대해 알아 보겠습니다.

Priority Queue를 구현 하는 방법

PQ 구현 방식	삽입 시간	삭제 시간
List	O(1)	O(N)
Heap	O(logN)	O(logN)

Heap 정렬 : N개의 데이터를 heap에 넣었다가 꺼내는 작업 -> O(NlogN)

정리 :

"Priority Queue를 구현하는 방법으로 Heap 모듈을 이용할 수 있다"

"데이터를 추가,삭제할 때 최악의 경우에도 시간복잡도 O(logN)로 힙의 성질을 유지할 수 있다는 장점이 있다. "

그렇다면 'Heap'은 뭘까?

Heap : 완전 이진 트리 자료구조의 일종 -> 항상 root node(트리에서 가장 위에 있는 노드)를 제거

- heap에는 min heap과 max heap 2가지 종류가 있는데 그 중에서 min heap에 대해서 자세히 다뤄보도록 하겠습니다.

Max heap : 루트 노드가 가장 큰 값을 가짐
Min heap : 루트 노드가 가장 작은 값을 가짐

트리에서 상위에 있는 노드를 부모노드, 하위에 있는 노드를 자식 노드라고 합니다.

원소 3은 5와 9의 부모 노드이며 , min heap은 부모노드가 항상 자식노드보다 작은 것을 만족시킵니다.

Heap의 구조에 대해서 알아보니, 처음에 궁금했던 삽입 순서에 대한 이해가 가기 시작했습니다.

[3,5,9,6] 으로만 이뤄져 있던 트리에 원소 4를 넣으니 min heap의 성질을 만족 시키기 위해(4는 5보다 작으니 상위로 올라가야겠다! ) 원소 4가 부모노드로 올라가는 것입니다. 밀려난 원소(5)는 원소 4가 있던 자식 노드로 자리가 바뀝니다.

heap에 원소를 집어 넣을 때 규칙을 알아보았습니다. heap에서 원소를 하나씩 꺼낼 때는 마찬가지로 min heap의 성질을 만족시켜야 합니다

밑의 코드와 결과를 보면 heapq.pop 함수를 통해서 가장 작은 원소부터 꺼내는 것을 확인 할 수 있습니다.

import heapq
heap_list = []
iterable =[3,5,9,6,4]

for value in iterable :
  heapq.heappush(heap_list,value)
  print(heap_list)

print("")
print("heapq.heappop함수를 이용해 데이터를 하나씩 꺼내보자")

result =[]
for i in range(len(heap_list)):
  result.append(heapq.heappop(heap_list))
  print(result)

[3]

[3, 5]

[3, 5, 9]

[3, 5, 9, 6]

[3, 4, 9, 6, 5]

heapq.heappop함수를 이용해 데이터를 하나씩 꺼내보자

[3]

[3, 4]

[3, 4, 5]

[3, 4, 5, 6]

[3, 4, 5, 6, 9]

요약

여태까지 우선순위 큐 자료구조와 이를 구현하기 위해 파이썬에서 사용할 수 있는 Heap 모듈에 대해서 알아 보았습니다.

최소값, 최대값을 계속 호출할 때 사용하는 우선순위 큐 자료구조를 구현할 때, heap 모듈을 사용하면 데이터를 추가,삭제할 때 최악의 경우에도 시간복잡도 O(logN)로 힙의 성질을 유지할 수 있다는 장점이 있습니다.

감사합니다.