(9) heap

우선순위큐는 완전이진트리 로 구현해야하고, 이는 heap 자료구조를 사용할 수 있다.

1. 우선순위 큐 구현 방법

구현 방법	enque	deque	특징
List	O(1)	O(n)	넣을 때는 바로, 뺄 때는 탐색
List	O(nlogn)	O(1)	넣을 때 정렬, 뺄 때 바로
완전 이진트리	O(logn)	O(logn)	넣을 때, 뺄 때 트리 탐색

2. List ↔ Complete Binary Tree

완전이진트리는 리스트로 변환이 가능하다. (반대도 가능)

항상 부모 노드가 i일 때, 자식 노드는 2i+1, 2i+2 이기 때문이다.

(주의, 형제 노드간에는 우선순위가 적용되지 않음)

3. Heap 자료구조

내장 함수	시간 복잡도
heapify	O(n)
heappop	O(logn)
heappush	O(logn)

from heapq import heapify, heappop

min_heap = [5, 3, 9, 4, 1, 2, 6]
heapify(min_heap) 
print(min_heap) # [1, 3, 2, 4, 5, 9, 6]
print(type(min_heap)) # list, 힙이라는 별도의 자료형은 없음

heappop(min_heap) # [2, 3, 6, 4, 5, 9]

heappop 할 때는, 루트 노드가 없어지면 가장 마지막 노드를 루트 노드로 대체하고

자식노드 중 우선순위가 가장 낮은 노드와 비교해서 shift down을 한다. (최대 H = logN 반복)

from heapq import heappush

heappush(min_heap, 1) # [1, 3, 2, 4, 5, 9, 6]

heappush 할 때는, 마지막 노드에 넣어주고

부모 노드와 비교해서 shift up 한다. (최대 H = logN 반복)

다익스트라 문제로 활용하는 경우가 많음.

다익스트라 정리

해당 시리즈의 포스트는 인프런에서 제공하는 개발남노씨의 코딩테스트 강의 를 바탕으로 작성하였습니다.