[자료구조] 힙 (Heap)

힙(Heap)이란?

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

 

 

특징

- 힙에는 최대 힙, 최소 힙 두 가지 종류의 힙이 있다.

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

 

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

- 형제 사이에서는 대소관계가 정해지지 않는다.

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

 

 

참고

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)