[파이썬] headq 모듈 사용

1. heapq

1. 사용 이유
   • 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬 heapq(힙큐)
2. 힙 자료구조
   • 자바의 PriorityQueue 와 유사
3. headq 모듈은
   • 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조
   • 인덱스 0 부터 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙 형태로 정렬된다
   • 사용법
     • heapq.heappush(heap,item) : item을 heap에 추가
     • heapq.heappop(heap) ; heap 에서 가장 작은 원소를 pop & 리턴. 비어있는 경우 indexErr
     • heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환 (in linear tiem, O(N))
   • 기본적으로 MinHeap 형태로 저장됨.
     • 원소의 추가시..

     import heapq
     
     heap = []
     heapq.heappush(heap, 50)
     heapq.heappush(heap, 10)
     heapq.heappush(heap, 20)
     
     print(heap)
     
     
     [10,50,20] ==>> minHeap

   • 최대 힙으로 변경하려면 별도의 과정이 필요
     • https://jungeun960.tistory.com/146
     + 최대 힙
     • heapq 모듈은 최소 힙만 동작하기 때문에 최대 힙으로 하기 위해 요령이 필요
     • 힙에 튜플(tuple)을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다
     • 따라서, 최대 힙을 만들려면 각 값에 대한 우선순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제하면 됩니다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 인덱스 1에 있는 값을 취하면 됩니다. (우선순위에는 관심이 없으므로 )