자료구조, heap

유동헌·2022년 1월 16일

💡 여러 블로그들을 보며 정리한 글입니다. 조금이라도 참고한 블로그에 대하여 출처를 남겨 놓았습니다.

heap의 개념

우선 순위 Queue를 위하여 만들어진 자료구조입니다.
배열을 이용하여 heap을 구현할 수 있습니다.
우선 순위 쿠는 배열, 연결리스트, 힙으로 구현이 가능합니다. 이 중에서 heap으로 구현하는 것이 가장 효울성이 좋습니다.

자료구조	삭제되는 요소
Stack	가장 최근에 들어온 데이터
Queue	가장 먼저 들어온 데이터
Priority Queue(heap)	가장 우선순위가 높은 데이터

우선순위 큐의 이용 사례

시뮬레이션 시스템
네트워크 트래픽 제어
운영 자체에서의 작업 스케쥴링
수치 해석적인 계산

자료구조 heap 이란?

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 구조입니다.
힙은 일종의 반정렬 상태를 유지합니다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨을 구성합니다.
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리를 말합니다.
- 이는 작은 수를 찾을 때 유용한 것 같습니다. 밑에서 다시 설명이 나오지만, 파이썬에서는 최소heap만 제공합니다. 최대heap을 사용하기 위해서는 밑에서 나오는 간단한 방법으로 구현이 가능합니다.
heap 트리에서는 중복된 값을 허용합니다(이진 탐색 트리에서는 중복된 값을 허용하지 않음)
키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않습니다.
시간복잡도는 O(log n)

heap의 종류

최대 heap

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모노드) ≥ key(자식 노드)
- 파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요합니다.

최소 heap

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모노드) ≤ key(자식노드)

heap의 구현

힙을 저장하는 표준적인 자료구조는 배열
구현을 쉽게 하기 위해서 배열의 첫 번째 인덱스인 0은 사용되지 않는다
- (블로그를 살펴보다 이러한 특성이 있다는 글을 보았는데, 아직까지 어떤 뜻인지 잘 이해가 되질 않습니다)
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않습니다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3입니다.

삽입 연산

삽입하고자 하는 값을 트리의 값을 마지막 원소에 추가합니다.
부모노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복합니다.

삭제 연산

힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거합니다.
가장 마지막 노드를 루트로 이동시킵니다.
자식 노드와 비교하여 조건이 만족할 때까지 이동시킵니다.

힙 추가

import heapq

# 원소를 추가하여 heap 자료형으로 만든다
heap = []

heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)

print(heap)

# 
[1, 2, 3, 4, 5]

이미 리스트가 있는 경우

# 이미 리스트가 있는 경우
heap_2 = [5,6,9,3,5,1]

heapq.heapify(heap_2)
print(heap_2)

#
[1, 3, 5, 6, 5, 9]

가장 작은 요소 삭제

# 가장 작은 요소가 삭제된다
heapq.heappop(heap_2)
print(heap_2)
heapq.heappop(heap_2)
print(heap_2)

#
[1, 3, 5, 6, 5, 9]
[3, 5, 5, 6, 9]
[5, 5, 9, 6]

최대힙 만들기

import heapq

# 튜플의 첫 번째 인자는 우선순위, 그러나 - 형태를 띄고 있기 떄문에 
heap_items = [1,3,5,7,9]

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

print(max_heap)

# heappop 사용시 가장 작은 요소를 리턴해야 한다. 하지만 우선순위를 반대로 했기 때문에 가장 큰 수가 리턴이 되는 것을 확인 가능하다. 
max_item = heapq.heappop(max_heap)
print(max_item)
# (-9, 9)

max_item = heapq.heappop(max_heap)[1]
print(max_item)
# 9

예제

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

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

# 
step1: [1,2] 합칩
       → [2, 3, 6, 4, 5, 7, 9, 8]
step2: [2,3] 합칩
       → [4, 5, 5, 8, 9, 7, 6]
---------------------------------------- 
result: 2
2

프로그래머스 더 맵게 풀이 과정

1. 첫 번째 실패

import heapq

def solution(scoville, K):
    
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 1:
        min_scoville_1 = heapq.heappop(scoville)
        
        if min_scoville_1 >= K:
            return answer
        
        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1
        
    return answer

런 타임 에러 발생 → 효율성 테스트 문제 발생

2. 프로그래머스 보고 고친 부분

import heapq

def solution(scoville, K):
    
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] <= K: <- 이 부분 수정
        min_scoville_1 = heapq.heappop(scoville)
        
        if min_scoville_1 >= K:
            return answer
        
        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1
        
    return answer

heapq를 사용하게 되면 heapify를 통해 heap 생성하게 되는데 이 때 sort를 하게 되면 heapify와 같아서 sort만 해도 됩니다
결정적으로 시간이 오래걸리는게 while 조건으로 min(scoville)이더라구요.
최솟값을 찾기 위해 배열 전체를 탐색해야 하니 그런 것 같습니다.
heappush를 하게 되면 알아서 최솟값이 배열 제일 앞으로 오게 되니 scoville[0]만 해도 됩니다.
(파이썬 내장 heapq는 최소힙이어서 최솟값이 제일 앞으로 오게 됩니다)

듣고 고쳤는데 효율성 테스트 다시 실패. 무엇이 문제일까?

문제에 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 이 조건도 고려해야돼요

3. 문제 최종 통과

def solution(scoville, K):

    answer = 0
    heapq.heapify(scoville)

    while len(scoville) >= 2:
        min_scoville_1 = heapq.heappop(scoville)

        if min_scoville_1 >= K:
            return answer

        else:
            min_scoville_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
            answer += 1

    if scoville[0] < K:
        return -1

    return answer

첫 번째 실패에서 while len(scoville) >= 2: 부분 때문에 실패한 것이라고 생각됩니다. 왜냐하면 가장 작은 값과 그 값보다 덜 작은 값이 성립이 되려면 리스트 안에는 최소 2개의 값이 있어야 하는데 그 경우에서 에러가 난 것 같습니다(확실하진 않습니다). 또한 if scoville[0] < K:\ return -1 이 부분도 추가를 하였습니다. 문제에 이미 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다 라는 조건이 있었는데 이를 무시하고 문제를 푸려고 해서 에러가 났던 것 같습니다.