자료구조 - Heap

 

자료구조 heap 은 완전 이진트리를 기반으로 하는 자료 구조입니다.

 

많은 값들 중에서 최소 혹은 최대 값을 빠르게 찾는것이 가능한 자료 구조입니다.

 

일반적으로 힙은 두 가지 타입이 존재합니다.

 

1. Max-Heap 

Max-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 커야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다.

 

 

예시 max-heap

 

2. Min-Heap

Min-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 작아야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다.

 

 

예시 min-heap

 

 

왜 힙을 쓰나요?

 

최대값 및 최솟값을 찾아내는 작업의 시간복잡도는 O(logN)으로 매우 빠릅니다.

 

새로운 원소를 저장하고 정렬하는데의 시간복잡도 또한 O(logN)으로 매우 빠릅니다.

 

그러므로 많은 데이터를  빠르게 저장하고 원하는 데이터를 빠르게 읽고 늘 정렬된 상태로 저장해 두려할때 많이 쓰이는 자료구조입니다.