[자료구조] 13. 힙(heap) 이해하기(feat. 구현 및 사용방법)

 

 

 

안녕하십니까 다제입니다. 

 

오늘은 힙(heap)에 대해서 알아보고자 합니다. 

 

Leetcode "k 경유지 내 가장 저렴한 항공권" 문제를 푸는 힙을 이용하여 푸는 풀이가 있었습니다.

 

그런데, 아무리 문제를 고민해도 풀 수가 없었습니다.

 

문제를 쪼개서 살펴보니 힙에 대한 개념이 잘 잡혀있지 않다는 사실을 알게되었고 이를 해결하기 위해 힙(heap)을 심도 깊게 공부해보았습니다. 

 

---

 

목차 

1. heap의 정의 

2. heapq.heappop(), heapq.heappush() 의 작동 방식 이해하기 

3. heap 구현하기(heapify)

4. heap 정렬 구현하기 

 

---

 

1. heap의 정의 

 - 완전 이진 트리이며, 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같은 자료구조를 말합니다. 

 - 즉 부모노드의 데이터 값이 자식노드의 값보다 크거나 같아야 하비다. 

 

---

 

2. heapq.heappop(), heapq.heappush() 의 작동 방식 이해하기 

 - 제가 heapq.heappop(), heapq.heappush()를 다루는 이유는 파이썬에서 제공하는 heap과 개념서에서 배우는 heap의 개념이 차이가 있었기 때문입니다. 

 - 공식문서에 설명되어 있는 일부분을 발췌해 왔습니다. 함께 보면서 이야기 나누어보시죠 

출처 : Python doc 

 - 공식문서에서도 말하듯 인덱싱이 0부터 되고 또한 가장 작은 항목부터 반환을 합니다. 저는 이부분 때문에 한참을 햇갈렸습니다. 코드를 보면서 함께 무슨 말이지 설명드리겠습니다. 

qwe = [5, 1, 3, -3]
print(qwe)
# 결과값 : [5, 1, 3, -3]

heapq.heapify(qwe)
print(qwe)
# 결과값 : [-3, 1, 3, 5]

 - 아니! heapify를 하게 되면 큰 순서대로 나와야하는데 파이썬에서는 작은 순서대로 나오는 겁니다. 

 - 응? 그러다가 heappop(), heappush()도 함께 살펴보았습니다. 

import heapq
heap = []
heapq.heappush(heap, 5)
print("1 :",heap) # print 결과값 => [5]
heapq.heappush(heap, 3)
print("2 :",heap) # print 결과값 => [3, 5]
heapq.heappush(heap, 1)
print("3 :",heap) # print 결과값 => [1, 5, 3]
heapq.heappush(heap, -3)
print("4 :",heap) # print 결과값 => [-3, 1, 3, 5]

 - 응? 작은 값부터 나오는구나. 내부적으로 heapsort가 작동되도록 구현이 되어 있더라구요 

 - 그러나, 코드를 직접 구현한 heap과 파이썬의 heap은 차이가 있다는 사실에 대해서 집고 넘어갈 필요가 있었습니다. 

 - 많은 블로그를 찾아보았지만, 이러한 디테일을 설명하는 곳이 없어서 포스팅하게 되었습니다. 

 

---

 

3. heap 구현하기(heapify)

 - 이제 heap의 작동 순서를 알아보고, 코드로 구현을 해보도록 하겠습니다. 

 - 작동 순서는 아래와 같습니다. 

  1) 부모 노드(heapify하려는 현재노드), 왼쪽 자식 노드, 오른쪽 자식 노드 중 가장 큰 값을 가진 노드를 파악합니다. 

  2) 1)에서 가장 큰 값을 가진 노드가 부모 노드라면 그 상태로 그대로 둡니다. 

  3) 가장 큰 값을 가진 노드가 자식 노드 중에 있다면 그 자식 노드와 부모 노드의 위치를 바꿔줍니다. 

  4) 기존의 부모노드가 자식 노드로 내려갔을 때, 다시 힙 속성을 어길 수 있습니다. 이에, 힙 속성이 충족될 때까지 위 단계를 반복합니다. 

# 일단 heap에서는 큰 값이 위로 오도록 위치를 교환해주는 함수가 필요합니다. 
# 간단하게 파이썬의 다중할당을 사용하여 구현합니다. 
# 여기서 tree는 list형식으로 이진 트리의 노드 값을 담고 있는 변수입니다. 
# index_1, index_2는 리스트의 인덱스 값 입니다. 
def swap(tree, index_1, index_2):
    """완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
    tree[index_2], tree[index_1] = tree[index_1], tree[index_2]

# 힙은 완전 이진트리이기 때문에 부모노드의 index값을 알면 자식노드의 값을 찾을 수 있습니다. 
# 이진트리에서는 부모노드 index x 2를 하면 왼쪽 자식노드를 찾을 수 있고 
# index X 2 + 1 를 하기 되면 오른쪽 자식노드를 찾을 수 있습니다. 
def heapify(tree, index, tree_size):
    """heapify 함수 구현하기"""
    # 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산합니다. 
    left_child_index = 2 * index
    right_child_index = 2 * index + 1
    # 일단 부모 노드의 값이 가장 크다고 설정합니다. 
    largest_index = index  

    # 왼쪽 자식 노드의 값과 부모노드의 값 비교
    # 곱하기를 하기 때문에 인덱스가 len(tree)보다 커지는 것을 방지하기 위한 코드도 함께 기재합니다. 
    # 자식노드가 부모노드 값보다 크다면 largest index를 부모노드에서 자식노드로 변경합니다. 
    if 0 < (left_child_index < tree_size) and (tree[largest_index] < tree[left_child_index]):
        largest_index = left_child_index

    # 오른쪽 자식 노드의 값과 부모노드의 값 비교
    # 곱하기를 하기 때문에 인덱스가 len(tree)보다 커지는 것을 방지하기 위한 코드도 함께 기재합니다. 
    # 자식노드가 부모노드 값보다 크다면 largest index를 부모노드에서 자식노드로 변경합니다. 
    if 0 < right_child_index < tree_size and tree[largest_index] < tree[right_child_index]:
        largest_index = right_child_index
    
    if largest_index != index: # 부모 노드의 값이 자식 노드의 값보다 작으면
        swap(tree, index, largest_index)  # 부모 노드와 최댓값을 가진 자식 노드의 위치를 바꿔준다
        heapify(tree, largest_index, tree_size)  # 자리가 바뀌어 자식 노드가 된 기존의 부모 노드를대상으로 또 heapify 함수를 호출한다
  
        

# 실행 코드
tree = [None, 15, 5, 12, 14, 9, 10, 6, 2, 11, 1]  # heapify하려고 하는 완전 이진 트리
heapify(tree, 2, len(tree))  # 노드 2에 heapify 호출


print(tree)
# 결과값 : [None, 15, 14, 12, 11, 9, 10, 6, 2, 5, 1]

 

---

 

4. heap 정렬 구현하기 

- 저희는 위에서 코드로 heap이 어떻게 구현되는지 살펴보았습니다. 

- 그런데, heap을 번호 순서대로 정렬을 하고 싶은데요 과연 어떻게 하면 될까요?

- 작동 원리는 다음과 같습니다. 

 1) 힙정렬을 하기 위해서는 일단 리스트를 힙으로 변경해주어야 합니다. 이 문제를 해결하기 위해서는 리스트의 맨 뒤에서부터 heapify를 해주면 됩니다. 

 2) 그렇다면 맨뒤쪽이 가장 작은 수이고 앞쪽이 가장 큰 수가 정렬된 상태가 됩니다. 

 3) 그럼 swap함수를 이용하여 맨 앞과 맨 뒤를 바꿔주고 바꿔준 맨 뒤를 제외한 나머지 값들만 heapify를 실행하면 됩니다. 

def heapsort(tree):
    """힙 정렬 함수"""
    tree_size = len(tree)

    # 마지막 인덱스부터 처음 인덱스까지 heapify를 호출한다 
    # 이를 통해 힙이 아닌 리스트를 힙 리스트로 변경한다
    for index in range(tree_size-1, 0, -1):
        heapify(tree, index, tree_size)

    # 마지막 인덱스부터 처음 인덱스까지
    for i in range(tree_size-1, 0, -1):
        swap(tree, 1, i)  # root 노드와 마지막 인덱스를 바꿔준 후
        heapify(tree, 1, i)  # root 노드에 heapify를 호출한다
        
        
# 입력값 : [None, 15, 5, 12, 14, 9, 10, 6, 2, 11, 1]
# 결과값 : [None, 1, 2, 5, 6, 9, 10, 11, 12, 14, 15]

 - swap과 heapify는 앞에 사용한 함수를 그대로 이용하여 사용합니다. 

 

지금까지 heapify에 대해서 알아보았습니다. 

 

이 개념을 이용하여 다시한번 leetcode를 풀어보시길 바랍니다. 

 

저도 다시 한번 풀어보아야 겠어요! 

 

오늘도 글을 읽어주셔서 감사드립니다.