[algorithm] heap [python]

파이썬 기본은 최소힙이다.

heappush

heapq.heappush(heap,item)

heap=[]에 item 추가

heappop

heapq.heappop(heap)

heap에서 가장 작은 원소를 pop & return
비어있으면 index error

heapify

heapq.heapify(x)

list x 를 heap 으로 변환 O(N)

최대힙만들기

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

주어진 리스트의 모든 값이 T 이상이 될 때까지 최솟값 두 개를 합치기

import heapq

def my_heap_example(L, T):
  """ 주어진 비커의 리스트를 힙 구조로 변환 """
  heapq.heapify(L) 

  result = 0

  while len(L) >= 2 : #IndexError 방지
      """ 힙에서 최솟값을 가져옴 """
      min_ = heapq.heappop(L) 
      
      if min_ >= T: # 액체의 최솟값이 T보다 크다는 조건 만족(종료)
        print("-"*40, "\nresult:", result)
        return result 
        
      else: # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입
        min_2 = heapq.heappop(L) 
        heapq.heappush(L, min_ + min_2)
        result += 1
        print("step{}: [{},{}] 합칩".format(result, min_ , min_2))
        print("       →", L)
  
  
  if L[0] > T:
    print("-"*40, "\nresult:", result)
    return result
    
  else:
    print("-"*40, "\nMission Failed")
    return -1

상남자식 코딩ㅋㅋ 

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    for i in range(1000000):
        try:
            heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
            if scoville[0] >= K: return i+1
        except:
            return -1