[자료구조] 힙 (Heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

힙에는 두가지 종류가 있다.

• 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 같거나 큼
• 최소 힙(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 같거나 작음

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

힙 리스트로 표현할 때

i 번째 노드의 왼쪽 자식 노드의 위치는 2i가 되며, 오른쪽 자식 노드의 위치는 2i+1이고

또한 i 번째 노드의 부모노드의 위치는 i/2 가 된다.