Heap with Python (파이썬으로 힙 자료구조 이용하기)

오늘은 자료구조 중의 하나인 Heap을 알아봅니다.

Heap의 영어단어 뜻은 '쌓다', '더미'라는 뜻입니다. 뭘 쌓는다는 의미인데 아무렇게나 쌓지는 않겠죠?

자주 사용하는 Stack과 Queue를 먼저 알아봅시다. 

Stack은 LIFO (Last In First Out)로 나중에 쌓은 순서대로 꺼냅니다. 반면에 Queue는 파이프와 같이 FIFO (First In First Out)로 먼저 들어간게 먼저 나옵니다. 

근데 문제는 이런 형태만 있는것이 아니라 , 쌓을때부터 순서를 고려해야 하는 경우도 있습니다. Stack 과 Queue가 쌓거나 넣은 순서대로 꺼낸다면 Priority Queue는 우선순위가 존재해서 우선 순위가 높은 데이터부터 꺼내도록 구현된 자료구조입니다.

Heap은 Priority Queue와 같이 우선 순위가 존재하는 자료구조 입니다.

1. Heap을 사용하는 이유

앞서 말한것 처럼 Priority Queue를 구현하기 위해 Heap이라는 자료구조를 사용합니다. 

배열에서 데이터의 최대, 최소값을 찾기위해서는 O(n)이 걸리는데 비해 Heap은 O(log n)으로 성능이 더 좋습니다.

2. Heap이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해  만들어진 완전이진트리입니다. Root에 최대값이 있는 Max Heap과 Root에 최소값이 있는 Min Heap으로 구분됩니다.

Max Heap의 경우 Heap의 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 커야 합니다. Heap은 좌측부터 채워나가지만  형제 노드들간에는 좌/우를 불문하고 크기를 구분하지 않습니다. Min Heap의 경우 반대로 각 노드의 값은 해당 노드들의 자식 노드가 가진 값보다 작아야 합니다.

- 이진트리 (binary tree) : 모든 노드들의 자식 노드가 두개 이하인 트리

- 완전이진트리(complete binary tree) :  부모, 왼쪽자식, 오른쪽 자식 순으로 채워지는 트리

3. Heap 과 Binary Search Tree의 차이

둘다 이진 트리입니다. Binary Search Tree는 왼쪽 자식 노드, 부모노드,  오른쪽 자식노드의  순으로 크기가 크지만 Heap은  순서가 없습니다. 

Binary Search Tree는 탐색용 자료구조, Heap은 최대, 최소 검색을 위한 자료구조로 사용됩니다.

4. Heap의 원리

Min Heap을 기준으로 설명합니다. 구글에서 검색해서 붙이려다 직접 그림도 다 그렸습니다 (미쳤다)

Max Heap은 반대입니다.

1. 값을 하나씩 트리의 노드에 좌에서 우로 할당. 
2. 부모노드의 값이 자식노드보다 크면 부모와 자식을 교체
3. 루트노드까지 비교를 반복

- Heap Tree에 2 , 6, 9, 4, 7, 1 의 순서로 데이터가 추가된다고 할때 아래와 같이 처리됩니다.

  

  

  

5. 파이썬에서 Heap 구현하기

(생략 ^^;;)

6. 파이썬에서 Heap 기능 사용하기

파이썬은 내장기능으로 heapq 를 제공하고 있습니다.

아래처럼 heapq를 사용하여 Heap을 사용할  수 있습니다. 문제는 heapq는 Min Heap의 기능만 제공합니다. (왜!!!)

import heapq

heap = []

heapq.heappush(heap, 2 )

heapq.heappush(heap, 6 )

heapq.heappush(heap, 9 )

heapq.heappush(heap, 4 )

heapq.heappush(heap, 7)

heapq.heappush(heap, 1)

print(heap)

### heap에  [1, 4, 2, 6, 7, 9]  요렇게 들어갑니다.

heap2 = [2,6,9,4,7,1]

heapq.heapify(heap2)

print(heap2)

### heapfy를 사용하면 heap2의 list가  [1, 4, 2, 6, 7, 9]의 heap구조로 바뀝니다.

while heap: 

    print(heapq.heappop(heap))

    print(heap)

### heappop을 사용하면 가장 작은 값을 하나씩 가져오며 heap은 하나씩 줄어듭니다.

### [1, 4, 2, 6, 7, 9] -> [2, 4, 9, 6, 7] -> [4, 6, 9, 7] -> [6, 7, 9] -> [7, 9] ->[9]

7. heapq로 Max Heap을 이용하기

값을 마이너스(-)로 바꾸면 가장 큰 값이 맨 처음에 나온다는 것을 이용하면 간단하게 Max Heap 을 구현할 수 있다.

list = [2,6,9,4,7,1]

heap3 = []

for item in list:

    heapq.heappush(heap3, -item)

print(heap3)

while heap3:

    print(heapq.heappop(heap3)*(-1))