[개념] 힙(Heap)
힙 : 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리
- 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽노드부터 차례대로 삽입
- 힙의 시간복잡도 : O(logn)
- 우선순위 큐와 같이 최댓값, 최소값을 빠르게 찾아야 하는 알고리즘에 사용
힙과 이진트리의 차이점
공통점 : 힙과 이진트리 모두 이진트리임.
차이점 :
- 이진 탐색 트리는 왼쪽 자식노드의 값이 가장 작고, 그 다음 부모노드, 그 다음 오른쪽 자식 노드의 값이 가장 큼
- 힙은 조건이 없음 즉 자식노드의 값이 오른쪽이 클수도, 왼쪽이 클수도 있음
- 이진 탐색 트리는 탐색을 위한 구조,
힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
활용
- 일반적으로 힙 구현시 배열 자료구조를 활용함.
- 힙 구현의 편리성을 위해 root 노드 인덱스 번호를 1로 지정하면, 수월함
1) 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
2) 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 2
3) 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 2 + 1
class Heap
def __inif__(self, data):
self.heap_array = list()
self.heap.append(None)
self.heap.append(data)
def insert(self, data):
if len(self.heap_array) == 0:
self.heap.append(None)
self.heap.append(data)
return True
힙 생성 & 원소 추가
heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.
아래 코드는 heap이라는 빈 리스트를 생성하고 50, 10, 20을 각각 추가하는 예시이다
import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap)
힙에서 원소 삭제
heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.
result = heapq.heappop(heap)
print(result)
print(heap)
최대 힙 만들기
파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.
IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.
힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. 이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.
아래의 예시는 리스트 heap_items에 있는 원소들을 max_heap이라는 최대 힙 자료구조로 만드는 코드이다.
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
print(max_heap)
Author And Source
이 문제에 관하여([개념] 힙(Heap)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dmsql698/개념-힙Heap저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)