힙?
힙의 기본 요구사항은 노드의 값이 그 자식 노드의 값보다 ≤ or ≥ 입니다. 이를 힙 속성(heap property)라고 합니다.
힙은 완전 이진 트리여야 합니다.
-
힙의 종류
-
최대 힙(max heap)
부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
-
최소 힙(min heap)
부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
-
-
******insert
heap에 새로운 원소를 추가할 때 어떻게 진행되는지 알아보겠습니다.
먼저 초기상태의 heap 구조입니다.
binary tree의 마지막 비어있는 공간에 원소를 추가합니다.
heap 구조인지 확인을 하고, heap 구조가 아니라면, heap 구조형태로 만들어줍니다.
위의 방식을 반복하여, 최종적인 heap 구조 형태를 얻어냅니다.
-
******delete
이번에는 heap에 원소를 제거할 때 어떻게 진행되는지 알아보겠습니다.
max heap 상태에서 원소를 제거할 때는 루트 노드가 제거됩니다.
루트 노드 자리를 가장 마지막 노드로 채워줍니다.
heap 구조인지 확인하고, 아니라면 heap 구조로 만들어줍니다.
-
******python heapq
python의 heapq를 이용하여 heap구조를 사용할 수 있습니다. 기본적으로 min heap으로 구현되어 있습니다.
import heapq heap = [] # 원소 추가 heapq.heappush(heap,1) heapq.heappush(heap,5) heapq.heappush(heap,2) heapq.heappush(heap,8) # 원소 제거 heapq.heappop(heap) heapq.heappop(heap) # list를 heap으로 변환 number_list = [4,5,7,3,6,3,1] heapq.heapify(number_list) # max heap number_list = [4,5,7,3,6,3,1] heap = [] for num in number_list: heapq.heappush(heap, (-num, num))