python 힙 자료구조 참고 링크
교재 대신 아기여우의 자기계발로그 티스토리를 참고하여 공부하였다.

Heap

: 힙은 특정한 규칙을 가진 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

Heap 특징

• 부모노드와 자식 노드 사이에는 대소 관계 성립한다.
• 그렇기 때문에 우선순위를 가지는 노드가 항상 루트에 오게 되고
  우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
• 키값의 대소관계는 부모-자식 관계에만 성립하고, 형제노드 사이의 대소 관계가 정해지지 않는다.

최소 Heap

: 부모 노드의 키값이 자식 노드의 키값보다 항상 작다.

최대 Heap

: 부모 노드의 키값이 자식 노드의 키값보다 항상 크다.

import heapq

import heapq

heap = []

heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
print(heap)

first_heap = [30 ,10, 20]
heapq.heapify(first_heap)

print(first_heap)

result = heapq.heappop(heap)
# heappop은 가장 작은 원소 힙에서 제거한 후, 제거한 값 결과값으로 리턴
print(result)
print(heap)

second_result = first_heap[0]
#가장 작은 원소 제거 없이 결과값으로 리턴
print(second_result)
print(first_heap)

최대 heap(최댓값 정렬)

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

max_heap = []
for item in heap_list:
  heapq.heappush(max_heap, (-item, item))
    #리스트 max_heap에 튜플 형식으로 값 넣기
  #튜플의 첫 번째 원소를 우선순위로 힙을 구성
  #item = -item(부호변경)이라 최댓값 정렬이 된다.

print(max_heap)
print(max_heap[0])

max_item = heapq.heappop(max_heap)[1]
#실제 원소 값은 튜플의 두 번째 자리이므로 인덱스 1이 최댓값
print(max_item)
print(max_heap)

#최대힙 또 다른 방법
import heapq

h = []
heapq.heappush(h, -3)	# 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, -9)	# 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, -7)
heapq.heappush(h, -8)	
heapq.heappush(h, -5)
heapq.heappush(h, -1)



for _ in range(6):
	print(-heapq.heappop(h))
    # 출력시-을 붙여준다.

예제로 개념 굳히기[비커 문제]

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

: N개의 비커에 액체가 담겨 있다. 모든 비커에 있는 액체의 양이 T 이상이 될 때까지 액체가 가장 적게 담긴 두 비커의 액체를 합쳐가려 한다. 각각의 비커에 담겨있는 액체의 양을 표기한 리스트 L과 기준 T가 주어질 때, 모든 비커의 양이 T 이상이 될 때까지 필요한 작업 횟수를 리턴하는 함수를 구현해보자. (구현할 수 없는 경우 -1을 리턴)

import heapq
T = int(input())
L = list(map(int, input().split()))
def beaker_problem(L,T):
    count = 0
    while len(L)>=2:

        heapq.heapify(L)
        min_beaker = heapq.heappop(L)
        if T <= min_beaker:
            return count
        else :
            total = 0
            min_beaker2 = heapq.heappop(L)
            total = min_beaker +min_beaker2
            count += 1
            heapq.heappush(L,total)

    if L[0] > T:
        print(count)
    else:
        print(-1)
print(beaker_problem(L,T))

코드 작성 중 오류

:while 문은 함수에 포함 시켜야 return 에러가 나지 않는다
return outside function error in python