최상단노드(부모노드) = root node => 노드중 가장 큰 값
- 최대힙 : 루트 노드(부모노드)에 제일 큰 값이 위치해있으면 max-heap(최대힙), 이 경우 자식노드는 무조건 부모노드보다 작음.
- 최소힙 : 루트 노드(부모노드)에 제일 작은 값이 위치해있으면 min-heap(최소힙), 이 경우 자식노드는 무조건 부모노드보다 큼.
Cpp에서는 max-heap, Python에서는 기본적으로 min-heap 제공
그래서 Python에서의 Priority Queue나 heapq에서 루트노드에는 모든 노드중에서 가장 작은 값이 위치할것이고, pop을 했을때 항상 가장 작은 값이 나오게 된다.
- 삽입/ 삭제 : O(log N)
from queue import PriorityQueue as pq
pq = pq()
pq.put(6)
pq.put(10)
pq.put(-5)
pq.put(0)
pq.put(8)
pq.put(2)
while not pq.empty():
print(pq.get())output :
-5
0
2
6
8
10하지만 이 친구도 thread-safe 한 성격을 가지고 있어서 속도가 느리다.
그래서 보통 heapq를 대부분 사용.
heapq의 기본정보
line 1 : heapq 모듈 불러오기
line 3 : 빈 리스트 선언해주기
line 4 : heapq의 기본적인 명령어
주로 사용하게 되는건 heappush, heappop
heapush(값을 넣어줄 리스트이름(pq), 넣을 값(6))
heappop(값을 pop할 리스트이름(pq))
리스트의 요소들은 heapq모듈이 push와 pop을 할때마다
0번째 index는 항상 최상단 Node(최솟값)이 오게된다
import heapq
pq = []
heapq.heappush(pq, 6)
heapq.heappush(pq, 12)
heapq.heappush(pq, 0)
heapq.heappush(pq, -5)
heapq.heappush(pq, 8)
print(pq)
while pq:
print(pq[0]) # 최상단(root node)출력
heapq.heappop(pq)Output :
[-5, 0, 6, 12, 8]
-5
0
6
8
12부모와 자식은 정렬되어도 자식과 자식간에는 대소관계가 없으므로 주의! 즉, index[0]과 index[1]은 정렬이 되지만, 그 나머지들은 대소관계를 판별할수가 없음
ex)첫번째 heappush에 6대신 9를 넣고 run한 output
[-5, 0, 9, 12, 2]최대힙 (max-heap) 만들기
파이썬은 최소힙만 지원하지때문에 최대힙을 구현할려면 약간의 트릭이 필요하다.
최소를 최대로 만들려면? 음수로 만들면됨.
ex) 1 < 9 | -1 > -9
원래값은 그대로 출력해줘야 하므로 비교값을 새로 만들어줘서 튜플로 묶고, 그 값만 비교를 하고 출력할때 비교값이 아닌 원래값, 그러니까 index[1] 만 출력을 해주면 max-heap이 된다.
import heapq as pq
number = list(map(int,input().split()))
heap = []
for num in number:
pq.heappush(heap,(-num, num))
while heap:
print((pq.heappop(heap)[1]),end=' ')Input :
-9 -3 -22 -1 2 88 6 51 920 0 -2
Output :
920 88 51 6 2 0 -1 -2 -3 -9 -22 
920이 pop되고 다시 index[0] = (부모노드)가 최댓값으로 정렬이 되는상황.
일개의 학부생이 강의듣고 요약하는거라 신뢰성이 떨어지는 글이므로 알아서 걸러 봐야함에 유의할것
