여름방학 도약수업 12일차
dictionary와 set을 배우고 우선순위 큐가 나왔다.
우선순위 큐가 뭐고…
큐는 앞에서 2100번 정도 사용해서 개념도 익숙하고 사용법도 익숙하다.
모르면 2학년 다시해라
(사실 우선순위 큐도 모르면 다시 해야하긴함)
일단 자료에는 우선순위가 가장 높은 데이터에만 관심이 있고, 이 데이터만 먼저 나갈 수 있는 형태의 자료구조라고 한다.
그리고 보통 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현이 된다.
그럼 힙 부터 알아보자…
힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료 구조이다.
(완전이진트리도 모르면 2학년 다시 하러 가라)
힙의 특징은 완전이진트리 형태로 이루어져 있고,
부모노드와 서브트리간 대소 관계가 성립된다 한다.
이게 뭔 말이노?
아, 최소힙 (min-heap) 최대힙 (max-heap)의 두 종류가 존재하는데,
최소힙은 부모 노드가 자식 노드보다 작거나 같고
최대힙은 부모 노드가 자식 노드보다 크거나 같다.
아하라 방구스 ~
근데 내가 구현을 알아보는 시간이 아니니까 어떻게 쓰는지를 알아보자.
python에서는 PriorityQueue라는 class가 존재하긴 한단다. 하지만 알고리즘 문제를 풀기 위해 나온 class가 아니라서 속도가 느리단다. (thread간의 synchronized를 맞춰야 하는 제약이 있다네요)
그래서 heapq를 사용한다함. heapq 사용을 위해서는 import heapq를 가장 위에 적어야 한다네요.
(자바스크립트로 다루는 방법은 다음에 책을 읽으면서 알아봅시다)
그리고 파이썬의 heapq는 min-heap 입니다.
파이썬의 heapq는 일반 리스트를 힙 처럼 다룰 수 있게 해주는 함수들의 모음이라네요.
heapq.heappush() : 힙에 원소 추가
heap=[]
heapq.heappush(heap,4)
이런 식입니다. 이헤가 되시죠
그럼, heappop(heap)
이건? 가장 작은 값이 사라지겠죠 왜냐 ?? 파이썬의 힙큐는 민힙이니까요 ㅇㅇ
오 근데 heapify 라는 것도 있네요
기존 리스트를 힙으로 바꾼다네요. heappush를 하는 것 보다 효율적이래요 ㄷㄷ
아 그럼 이제 어떻게 굴러가는지 이해가 된다 그죠
감사합니다.
