Heap이란?
- Heap의 영어단어 뜻은 '쌓다', '더미' 라는 뜻
- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리
- 이진트리(binary tree) : 모든 노드들의 자식 노드가 두개 이하인 트리
- 완전이진트리(complete binary tree) : 부모, 왼쪽자식, 오른쪽자식 순으로 채워지는 트리
- 루트에 최대값이 있는 Max Heap과 루트에 최소값이 있는 Min Heap으로 구분됨
- Max Heap의 경우 Heap의 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 커야함
- Min Heap의 경우 반대로 각 노드의 값은 해당 노드들의 자식 노드가 가진 값보다 작아야함
- Heap은 좌측부터 채워나가지만 형제 노드들간에는 좌/우 불문하고 크기를 구분하지 않음
Heap과 Binary Search Tree의 차이
- 둘다 이진트리이다.
- Binary Search Tree는 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드의 순으로 크기가 큼
- Heap은 크기 순서가 없음 => 루트값만 고정 => 최소힙이면 루트값이 최소값, 최대힙이면 루트값이 최대값
- 따라서, Binary Search Tree는 탐색용 자료구조에 사용. Heap은 최대, 최소 검색을 위한 자료구조로 사용
Heapfify란?
- heapify는 일반 배열을 heap 자료구조로 만드는 과정
Min Heap 예시
- [2, 6, 9, 4, 7, 1] 순으로 데이터가 추가될때 Min Heap 구조로는 다음과 같이 처리된다 => [1, 4, 2, 6, 7, 9]
Python Heap 사용
heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공자바에 익숙하신 분이라면PriorityQueue 클래스를 생각하시면 이해가 쉬우실 것 같습니다.- min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치
사용
- heap은 list만들때와 같음 =>
heap = []=> 이상태에서 heapq 모듈의 메소드를 사용하면 heap구조를 사용하는것 - 최소힙에선 idx 0 => 최소값 / 최대힙에선 idx 0 => 최대값
- (주의사항) 최소힙에서 인덱스 0에 가장 작은 원소가 있다고 해서, 인덱스 1에 두번째 작은 원소, 인덱스 2에 세번째 작은 원소가 있다는 보장은 없다는 것입니다.
- 시간복잡도
- 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O()의 시간 복잡도를 가집니다.
# 모듈 임포트
import heapq
# heap은 list만들때와 같음 => 메소드사용이 다르다고 생각하자
heap = []
# heap에 원소추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
#[1, 3, 7, 4]
# 힙에서 원소 삭제
print(heapq.heappop(heap))
#1
print(heap)
#[3, 4, 7]
# 아래 코드를 통해서 가장 작았던 1이 삭제되어 리턴되었고, 그 다음으로 작었던 3이 인덱스 0으로 올라온 것을 확인 가능
print(heapq.heappop(heap))
#3
print(heap)
#[4,7]
# 최소값 선택하는 방법(pop처럼 삭제하는게 아니라 그냥 조회만 한다 or 그냥가져온다)
print(heap[0])
#4
# 기존 시르스틀 힙으로 변환해주기(heapify)
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)
#[1, 3, 5, 4, 8, 7](참고) 최대힙은 어떻게 사용?
- 최대 힙을 만들려면 각 값에 대한 우선 순위를 담는 튜플을 만들어서 힙에다 담아주면된다.
- 이때 튜플은
(우선 순위, 값)형태인데(-값, 값)으로 넣어주면값이 클수록 우선수위-값은 작아져서 우선순위가 높아져서 => 최대힙 구조를 얻을 수 있음 - 그리고 이 힙에는 튜플들이 담겨있기때문에 값(value)를 가져오고 싶을땐 for문/while문으로 element를 하나씩 가져와서 값(value)이 있는 idx 1을 선택하면 됨
import heapq
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heapq.heappush(heap, (-num, num)) # (우선 순위, 값)
while heap:
print(heapq.heappop(heap)[1]) # index 1References
oneofakindscene