[이론] 자료 구조: 힙 heap

힙이란
(1-1) '부모의 값이 자식의 값보다 항상 크다'라는 조건을 만족하는 -> 최대 힙
(1-2) '부모의 값이 자식의 값보다 항상 작다'라는 조건을 만족하는 -> 최소 힙
(2) 완전 이진 트리이다.
 
완전 이진 트리는
(1) 마지막 레벨을 제외한 모든 레벨에서 노드가 가득 차 있고
(2) 마지막 레벨에서는 왼쪽부터 차례대로 노드를 채우는
이진 트리이다.
 
<예시>
       1                - 레벨 0 (루트: 최상단 노드)
     /   \
   2    3             - 레벨 1
  / \    /
4   5 6             - 레벨 2 (현재 마지막 레벨)
 
위 그림은 부모의 값이 자식의 값보다 항상 작은 최소 힙의 그림입니다.

힙의 특징

1. 
이진 트리에서 부모가 같은 자식들을 형제 노드라고 한다. 힙에서 형제 사이의 대소 관계는 일정하지 않다. 
 
<예시>
       1
     /   \
   3    5
  / \    / \
7   6 8  9
 
위 그림은 형제 사이의 대소 관계가 일정하지 않은 최소 힙의 그림이다. 마지막 레벨의 노드들을 부모 노드와 비교해 보자. 7과 6은 부모 노드인 3보다 크고, 8과 9는 부모 노드인 5보다 크다. 이번에는 마지막 레벨에서 같은 부모를 둔 두 자식 노드들을 비교해보자. 3을 부모로 둔 자식 노드들을 보면 왼쪽에 큰 숫자 7이, 오른쪽에 작은 숫자 6이 오고 있다. 그런데 5를 부모로 둔 자식 노드들을 보면 왼쪽에 작은 숫자 8이, 오른쪽에 큰 숫자 9가 오고 있다. 이처럼 힙에서는 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 이런 점 때문에 힙은 부분 순서 트리라고도 한다.
 
2.
힙의 원소를 리스트에 저장하면 다음과 같은 모양이 된다. 아래 있는 리스트는 위에 있는 힙 그림을 리스트로 표현한 것이다.
 
<예시>
리스트      [    1    ][    3    ][    5    ][    7    ][    6    ][    8    ][    9    ]
인덱스           0           1           2           3          4           5           6
 
힙에서 부모 노드의 인덱스와 자식 노드의 인덱스 사이에는 다음과 같은 관계가 성립한다.
 
원소 a[i]에 대하여
- 부모:               a[(i - 1) // 2]
- 왼쪽 자식:       a[i * 2 + 1]
- 오른쪽 자식:    a[i * 2 + 2]