자료구조(5)_Heap

Heap ?

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

- 힙 속성(property)는 다음과 같다. 

* A가 B의 부모노드(parent node)이면, A의 키(Key)값과 B의 키값 사이에는 대소관계가 성립한다. 

- 힙에는 두가지 종류가 있고 , 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙' 이라 하고 , 보모노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 '최소 힙' 이라 한다. 

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

- 각 노드의 자식노드의 최대 개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 '이진 합(binary heap)을 사용한다. 

- 힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 

최대 힙의 예시

자식노드의 개수가 최대 2개인 가장 많이 사용하는 이진 합(binary heap) ?

- 이진 힙은 내부노드(internal node)에 키(key)와 요소(element)를 저장한 이진 트리로 다음과 같은 두 가지 특징을 갖는다. 

 1. 뿌리노드를 제외한 각 내부는 키값이 오름차순이거나 내림차순이다.

 2. 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다. 

 * 이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조

 

- 힙은 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 O(n)만큼 시간이 걸리지만 힙을 사용하면 O(logn)만큼 소요되기 때문에 배열을 사용할 때 보다 더 빠르게 최소값과 최댓값을 구할 수 있다.