자료구조 - 힙(Heap)

힙(Heap)이란?

'완전 이진 트리'의 한 종류로, 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 자료구조

완전 이진 트리란?

• 포화 이진 트리에서 오른쪽 부터 잎이 제거된 형태의 트리 자료구조
• 왼쪽 노드부터 채우는 형식

이진트리의 특성상, 부모 노드와 자식 노드간의 관계에는 일정한 규칙이 존재한다.

a라는 리스트가 있다고 가정할 때,

• a[i]의 자식 노드는 a[2i], a[2i+1]에 존재한다.
• a[j]의 부모 노드는 a[j//2]이다.

힙의 종류는 대표적으로 2가지가 존재한다.

1. 최소 힙
   • 부모 노드가 자식 노드보다 반드시 작은 값을 가져야 하는 힙 구조
2. 최대 힙
   • 부모 노드가 자식 노드보다 반드시 큰 값을 가져야 하는 힙 구조

ex) 13, 88, 112, 35, 49, 17 이 입력값으로 들어오는 경우(최소 힙),

1. 순서대로 입력값을 트리에 삽입한다.
   • 13-88-112-35-49-17
2. 부모 노드가 자식 노드보다 큰 경우, 서로를 바꾼다.
   • 13-35-112-88-49-17
   • 13-35-17-88-49-112

위와 같이 힙 구조는 맨 앞에 오는 원소의 값이 반드시 최소 혹은 최대 값이 되므로 '우선순위 큐'를 사용한 알고리즘(e.g. Dijkstra)에 활용하기 적절하다.

Python에서 '최소 힙' 사용하기

Python에서는 built-in 라이브러리 heapq를 활용해 heap자료구조를 사용할 수 있다.
import heapq

• heapq.heappush

  • heap 구조를 가진 배열에 새로운 원소를 맨 마지막 자리에 집어넣고 최소 힙의 성질을 만족할때 까지 위치를 바꾼다.
    

    heap = [3, 4, 6, 8, 5, 7]
    heapq.heappush(heap, 2)
    print(heap)  
    # output : 2, 4, 3, 8, 5, 7, 6

• heapq.heappop

  • heap 구조를 가진 배열에서의 최상위 노드를 추출하고, 재정렬 수행.
    

    heap = [3, 4, 6, 8, 5, 7]
    data = heapq.heappop(heap)
    print(data)  
    # output : 3
    print(heap)  
    # output : 4, 5, 8, 6, 7