[Python] heqpq를 이용한 힙(heap)자료구조

Heap 자료구조

- 완전 이진트리의 일종이다.

- 중복된 값을 허용

- 최댓값, 최솟값을 빠르게 찾아내기 위한 자료 구조이다. (우선순위 큐)

 

파이썬의 heapq 모듈

- heappush: 힙에 값을 추가, 추가 후에 정렬이 되지 않는다.

- heappop: 힙에서 가장 작은 값을 꺼내옴

- heapify: 리스트를 힙으로 변환

 

프로그래머스 더맵게 문제 heapq 적용

프로그래머스

import heapq

def solution(scoville, K):
  answer = 0
  heapq.heapify(scoville)
  while 1:
    if len(scoville)<=1 and scoville[0] < K:
      answer = -1
      break
    if scoville[0] >= K:
      break
    new_num = heapq.heappop(scoville) + (heapq.heappop(scoville)*2)
    heapq.heappush(scoville, new_num)
    answer+=1
  return answer