힙 모듈(heapq)

heapq 모듈은 자료를 오름차순으로 정렬하여 저장할 수 있으며, 작은 수 부터 pop이 되는 구조로 이루어져 있다.

간단히 말하여 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이라고 생각하면 쉽다.

       <출처: [<https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>](<https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>)>  

힙 기본 구조

import heapq
heap = []

힙 모듈 사용 방법

스택과 마찬가지로 힙도 push, pop를 사용할 수 있다.

• heapq.heappush(리스트명, 넣을 값)

  heapq.heappush(heap,50)
  heapq.heappush(heap,30)
  heapq.heappush(heap,20)
  print(heap)
  
  #결괏괎
  [20, 30, 50]
  

• heapq.heappop(리스트명)

  가장 작은 원소를 pop하고 리턴한다. 비어 있는 경우 IndexError가 호출된다.

  heapq.heappop(heap)
  
  #결괏값
  20
  

• heapq.heapify(이미 값이 존재하는 리스트명)

  원래 있던 리스트 값을 heap으로 즉각적으로 변화시킨다. 시간복잡도는 O(N) 방식이다.

최대 힙 만들기

입력값에 튜플값 (-x, x) 를 넣어주게 되면 -x 값을 기준으로 오름차순이 되기 때문에 pop을 했을 경우에 heap[1]에서 최대값을 얻어 낼 수 있다.

for item in heap_list :
	heapq.heapqush(heap,(-item, item))