[자료구조] heap

힙(heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이다. 

 

* 완전이진트리 : 자식노드가 2개 이하인 이진 트리구조

1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다

키 값의 대소관계는 부모노드와 자식노드 간에만 성립하며 형제 사이에는 대소관계가 정해져 있지 않다. 

 

최대 힙(max heap) : 부모 >= 자식, 루트노드 == 최댓값 -> 이거 할라구 사용하는거!! 

최소 힙(min heap): 부모 <= 부모, 로트노드 == 최솟값 -> 이거 할라구 사용하는거!! 

데이터 삽입

데이터 삭제

힙 생성 알고리즘(Heapify Algorithm)

이진트리에서 힙 구조를 만족하지 않는 노드를 재 정렬하여 트리전체를 힙 구조로 만드는 것 

노드 한 개에 대해 수행할 시 시간복잡도는 O(log N)

 

 

힙 정렬(heap-sort)

완전 이진트리에서 모든 노드에대해 힙 생성 알고리즘(Heapify Algorithm)을 수행하여 최대힙 또는 최소힙을 구성하고 이후 루트노드부터 하나씩 빼와서 정렬하는 방법 

시간복잡도는 O(N * log N)

heap 만들기

heap 정렬

문제) 

더 맵게 

 

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

입출력 예)

scoville = [1, 2, 3, 9, 10, 12]

K = 7

return = 2

import heapq

def solution(scoville, K):
    
    s = scoville
    count = 0
    heapq.heapify(s)
    
    while s[0] < K and len(s) > 1:
        x = heapq.heappop(s)
        y = heapq.heappop(s)
        z = x + (y*2)
        count += 1
        heapq.heappush(s,z)
    
    if s[0] >= K:
        return count
    else:
        return -1
    
#     heap을 사용하지 않은 코드 -> 실패    
#     if s[0] >= K:
#         return 0
#     count = 0
#     while s[0] < K and len(s) > 1:
#         s.sort
#         if len(s) > 2:
#             x = s[0] + s[1]*2
#             count += 1
#             s = [x] + s[2:]
#         elif len(s) == 2:
#             s = [s[0] + s[1]*2]
#             count += 1
     
#     if s[0] >= K:
#         return count
#     else:
#         return -1

파이썬의 heapq는 리스트를 최소힙으로 바꾸어준다. heap[0] 루트노드에는 항상 최소값이 위치하게 한다. 

 

heapq.heapify(lst) -> lst를 heap구조로 바꿔줌

heapq.heapush(lst, s) -> heap 삽입

heapq.heapop(lst, s) -> heap 에서 부모노드 꺼내기

heap[0] -> 루트노드(최소값)에 접근