[파이썬] 힙(Heap) 이란

힙이란?

트리 구조 주에서 완전이진트리를 기반으로 하는 자료구조이다. 힙은 최댓값과 최솟값을 구하는데 유용하다.

 

만족 조건

1. 자식노드보다 부모노드의 값이 더 커야한다
2. 왼쪽 자식노드보다 오른쪽 자식노드의 값이 더 커야 한다

 

최소 힙

부모노드의 값이 자식노드의 값보다 항상 작은 힙

최대 힙

부모노드의 값이 자식노드의 값보다 항상 큰 힙

---

라이브러리(모듈) 불러오기

- heapq 라이브러리는 최소힙(min heap)으로만 동작하기 때문에, 최대힙(max heap)으로 활용하려면 요령이 필요하다. 

- 즉, 일반적으로는 최소힙으로 생각하면 된다

import heapq

리스트를 힙으로 바꾸기

- .heapify(list) 사용하기

list1 = [1, 2, 3, 4]
heapq.heapify(list1)

print(list1)
>>> [1, 2, 3, 4]

힙 생성 및 원소 추가

- 힙은 완전이진트리 구조를 갖는다

- 50, 10, 20 순서대로 넣는 다고 [50, 10, 20] 이라는 나오지 않고, [10, 50, 20] 이라고 나오게 된다

- 최소힙(min heap)의 조건에 따라 [10, 50, 20]이 된다

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)
>>> [10, 50, 20]

힙 원소 삭제

- 가장 작은 원소를 힙에서 제거함과 동시에 결과값을 리턴한다

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap) 
>>> [10, 50, 20]

heapq.heappop(heap)
print(heap)
>>> [20, 50]

heapq.heappop(heap)
print(heap)
>>> [50]

heapq.heappop(heap)
print(heap)
>>> []

힙 시간복잡도

O(logN)

---

힙 시각화 사이트

1. visualgo 사이트에 접속한다
2. Binary Heap을 클릭한다
3. 설명서는 읽어도 되고, 안읽어도 된다
4. 좌측 하단에 보면 "Create(A)-O(NlogN)"을 클릭한다(참고로 최대힙임)
5. "A= 원하는 값을 넣기" 원하는 값을 넣고, Go를 누르면 실행된다

https://visualgo.net/en

visualising data structures and algorithms through animation - VisuAlgo

---

최대힙 만드는 방법은 다른 블로그에도 많으니 찾아보면 된다