힙(Heap)

힙(Heap)

- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조

- 키 값의 대소 관계는 오로지 부모노드와 자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다

- 각 노드의 자식 노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 자식 노드의 개수가 최대 2개인 이진 힙을 사용한다

- 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에 오게 되는 특징을 갖는다

- 루트 노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있다

- 따라서 힙 구조에서의 최댓값(혹은 최솟값)을 찾을 때의 시간복잡도는 O(1)이다

- 데이터의 삽입과 삭제는 모두 O(logN)이 소요된다

- 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다

 

힙의 종류

최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리로 가장 큰 값을 루트 노드가 갖는다

 

최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 작은 완전 이진트리로 가장 작은 값을 루트 노드가 갖는다