힙(Heap)

▶힙(Heap)

---

우선순위가 가장 높은 키에 접근이 빈번한 경우 사용되는 자료구조이다.

힙은 반드시 아래의 두 가지 속성을 만족해야 한다.

1. 완전 이진트리(Complete binary tree) 형태이다. (노드들이 왼쪽부터 빠짐없이 채워져 있어야 함, 가득 차지 않아도 됨)

2. 각 노드의 값은 자신의 자식 노드들의 값보다 크거나 같다. (OR 작거나 같다.) 

▶Heapify

---

heap 자료구조의 속성이 깨졌을 때 이를 만족시키기 위해 수행하는 연산. 

위에서 아래로 혹은 아래에서 위로 수행할 수 있다. (삽입시 수행)

O(logN)의 시간이 걸린다.

아래에서 위로 수행하는 경우 해당 노드의 키가 부모 노드보다 크거나 같은지(OR 작거나 같은지)를 확인하여 결과가 true인 경우 키 값을 swap하고, 위에서 아래로 수행하는 경우 해당 노드의 키가 자식 노드들보다 작거나 같은지(OR 크거나 같은지)를 확인하여 해당 노드의 키 값보다 큰 자식과 키 값을 swap한다. swap이 되었다면 바뀐 위치에서 계속해서 비교를 진행하며 swap이 가능한 동안 계속 수행한다. 그러고 나면 모든 노드가 heap의 속성을 만족하게 된다.

▶Insert

---

마지막 노드 다음의 인덱스에 키를 저장하고 아래에서 위로 heapify를 수행한다. O(logN)의 시간이 걸린다.

▶Delete

---

루트 노드를 삭제하고 마지막에 있는 노드를 루트노드로 가져와서 위에서 아래로 heapify를 수행한다. 삭제하는 연산은 마지막에 있는 노드를 루트 노드에 덮어쓰면 되므로 O(1)의 시간이 걸리고 heapify에 O(logN)의 시간이 걸리므로 전체적으로 O(logN)의 시간이 걸린다.

▶Build heap 

---

주어진 정렬되지 않은 데이터들을 heap 속성에 맞게 정렬하는 것을 말한다.

[기본적인 방법] → O(NlogN)

1. N개의 데이터에 대해 insert를 수행한다.  

[좀 더 빠른 방법] → O(N)

1. 배열에 정렬되지 않은 채로 N개의 데이터를 담는다.

2. N/2번째 노드(단말 노드가 아닌 노드들 중 마지막에 위치한 노드)부터 첫 번째 노드(루트 노드)까지 아래 방향으로 heapify를 수행한다. 

▶소스 코드