소립의 컴퓨터실

1. Heap

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 "완전 이진 트리" (Complete binary tree) (완전 이진 트리 - 최하위 레벨을 제외한 모든 레벨에 노드가 모두 존재 한다.)

2. 속성

• 부모 노드의 키 값이 자식 노드들의 키 값보다 항상 크다. (최대 힙)
• 부모 노드의 키 값이 자식 노드들의 키 값보다 항상 작다. (최소 힙) (힙은 부모 자식간에서만 대소 관계가 성립된다. - 형제 간의 대소 관계 성립 X )

  루트 노드가 항상 우선순위(가장 높거나 가장 낮은 값)가 가장 높다는 것이 보장된다.

3. 힙은 우선순위 큐로 구현될 수 있다.

4. Adding

1. 가장 하위 레벨에 제일 왼쪽 노드에 추가할 데이터를 추가한다.
2. 추가된 데이터(new node)는 현재 자신의 부모 노드와 값(우선순위)을 비교한다.
3. 부모 노드가 자신(new node)보다 우선순위가 낮다면 swapping
4. 자신 보다 높은 우선순위를 가진 부모 노드를 만나기 전 까지 반복한다. --> 새로운 노드가 추가 되었을 때, 최하위 레벨에서부터 우선순위를 비교하며 위로 올라가는 과정을 "reheapification Upward"라고 한다.

5. Removing

1. 루트 노드가 가장 높은 우선순위를 가지기 때문에, 항상 루드 노드를 제거한다.
2. 제거 후, 완전 이진 트리 속성을 유지하기 위해 재구성을 진행한다.
3. 최하위의 가장 오른쪽에 있는 노드(last node)를 로트 노드로 복사 후, 원래의 노드(복사 된 노드)를 삭제한다.
4. 루트 노드는 왼쪽, 오른쪽 자식 노드와 우선순위를 비교하여, 자식의 우선순위가 자신보다 더 높으면 교환한다.
5. 자신 보다 낮은 우선순위를 가진 자식 노드들을 만나기 전까지 반복한다. --> 위에서부터 우선순위를 비교하며 아래로 내려오면서 자리를 찾아가는 과정을 "reheapification Downward"라고 한다.

6. 구현

• 힙은 "완전 이진 트리"이기 때문에, 배열로 구현하였을 때, Index당 노드의 위치가 정해져 있기 때문에 접근에 용이하다.

• 인터넷에서 어떤 곳은 배열 0번째 인덱스에 rood node를 저장하고, 어떤 곳은 1번째 인덱스에 rood node를 저장한다.. 
• http://stackoverflow.com/questions/9462003/why-is-element-zero-of-a-heap-array-not-used

- >그래서 찾아봄.... 그냥 사람들 마음대로라는 것 같은데.. 둘다 해도 되는 것같다~

• 0번째 인덱스에 Rood Node를 저장한 경우

1. k 인덱스의 왼쪽 자식 노드 인덱스 : 2k+1
2. k 인덱스의 오른쪽 자식 노드 인덱스 : 2k+2
3. k 인덱스의 부모 노드 인덱스 : (k-1)/2

• 1번째 인덱스에 Root Node를 저장한 경우

1. k 인덱스의 왼쪽 자식 노드 인덱스 : 2k
2. k 인덱스의 오른쪽 자식 노드 인덱스 : 2k+1
3. k 인덱스의 부모 노드 인덱스 : k/2

7. 힙 정렬 & 시간 복잡도

1. 정렬되지 않는 원소로 완전 이진 트리를 만들고, 최대(최소) 힙을 구성한다.
2. 최소의 힙인 경우, 루트의 값을 배열 인덱스 1에 저장 (최대 일 경우 맨 마지막 인덱스에 저장)
3. 다시 최대(최소) 힙 재구성

• 평균시간 복잡도 O(NlogN) : 완전 이진 트리를 힙으로 구성하는 평균 시간 O(logN) && n개의 노드에 대해서 n번의 힙 재구성이 이루어짐