[자료구조] 힙 (Heap)

힙(Heap)이란?

(사진출처 https://creativecommons.org/licenses/by-nc/2.0/kr/)

우선순위 큐를 구현하는 데 사용되는 중요한 자료구조입니다.
힙은 완전이진트리(Complete Binary Tree) 구조를 가지며, 부모 노드의 값이 자식 노드의 값보다 항상 크거나(최대 힙) 작은(최소 힙) 특성을 만족합니다.

최대 힙 (Max Heap)

• 부모 노드의 값이 자식 노드의 값보다 크거나 같은 특성을 갖습니다.
• 트리의 루트에는 최댓값이 위치합니다.

최소 힙 (Min Heap)

• 부모 노드의 값이 자식 노드의 값보다 작거나 같은 특성을 갖습니다.
• 트리의 루트에는 최솟값이 위치합니다.

힙의 주요 연산

삽입 (Insert)

새로운 원소를 힙에 추가합니다. 이 과정에서 힙 특성을 유지합니다.

삭제 (Delete)

최대 힙에서는 최댓값을 삭제하고, 최소 힙에서는 최솟값을 삭제합니다. 이 역시 힙 특성을 유지하며 수행됩니다.

힙ify (Heapify)

주어진 배열을 힙 특성을 만족하도록 변경합니다. 보통 특정 노드부터 시작하여 하향식 또는 상향식으로 힙 특성을 만족시킵니다.

힙의 시간 복잡도

• 삽입: O(log n)
• 삭제: O(log n)
• 힙ify: O(n)

표현

힙은 이진트리를 사용하므로 배열로도 효과적으로 구현할 수 있습니다.
일반적으로 배열의 인덱스 0부터 시작하면 부모와 자식의 인덱스 관계는 다음과 같습니다

부모 인덱스 (parent): i
왼쪽 자식 인덱스 (left child): 2i + 1
오른쪽 자식 인덱스 (right child): 2i + 2

데이터 삽입

(사진출처 https://creativecommons.org/licenses/by-nc/2.0/kr/)

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
   (부모노드는 삽입된 위치의 인덱스 번호에서 /2를 하면 쉽게 구할 수 있다.)
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

데이터 삭제

(사진출처 https://creativecommons.org/licenses/by-nc/2.0/kr/)

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드와 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

• 최대 힙
  1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

• 최소 힙
  1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

5. 조건을 만족할 때까지 4의 과정을 반복한다.