[자료구조] 힙

 Heap

 

힙 자료구조 

힙이란? 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로함

배열에 데이터를 넣고, 최대값과 최솟값을 빠르게 찾기 위해서는 O(n)이 걸리지만, 힙에 데이터를 넣고 최댓값과 최솟값을 찾으면 O(logn)이 걸림 

 

힙 property?

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

최대 힙? 부모 노드의 키 값이 자식 노드의 키값보다 항상 큰 힙 

-> 이러한 속성으로 힙에서는 가장 낮거나 높은 우선순위를 가지는 노드가 항상 루트에 오게됨 

-> 이를 통해 우선순위큐와 같은 추상적 자료형을 구현할 수 있음 

 

힙 함수 활용하기

heapq.heappush(heap, item): item을 heap에 추가

heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴, 비어 있는 경우 IndexError 호출

heapq.heapfy(x) : 리스트 x를 즉각적으로 heap으로 변환 O(N) 

 

1) 최소힙 예제 

- pyhon은 기본적으로 최소힙으로 구성되어 있음 

heap = [30,5,50,10,20]
heapq.heapify(heap)
print(heap) #[5, 10, 50, 30, 20]
print(heapq.heappop(heap)) #5

 

2) 최대힙 예제

- 최대힙을 사용하려면 _heapify_max 사용 필요

 heap = [30,5,50,10,20]
heapq._heapify_max(heap);
print(heap) #[50, 20, 30, 10, 5]
print(heapq._heappop_max(heap)) #50

 

3) heappush 예제

heap = [3,1,4,4,6,7,2];
heapq.heapify(heap);
print(heapq.heappop(heap)) #1 
print(heap) # [2, 3, 4, 4, 6, 7]

heapq.heappush(heap,-1);
print(heap) #[-1, 3, 2, 4, 6, 7, 4]