알고리즘 분석 | Heap 힙 데이터 구조 | Heap 삽입과 삭제

이전 포스팅

알고리즘 분석 | 자료구조 | 이진트리 종류 | Full binary | Complete binary

---

Heap 힙 데이터 구조

힙(Heap)은 내부 노드에 키(Key)를 저장하며 다음과 같은 성질을 만족하는 이진트리(Binary Tree) 구조를 말합니다:

1. 힙 순서(Heap Order) : 루트를 제외한 모든 내부 노드 v 에 대해서 key(v) ≥ key(parent(v)) 가 성립합니다.
   즉, 모든 내부 노드의 키는 그것의 부모 노드의 키보다 크거나 같습니다.
   미니 힙(Min Heap): 의 경우 부모 노드의 키 값이 항상 자식 노드의 키 값보다 작거나 같음을 의미합니다.
   맥스 힙(Max Heap): 의 경우 부모 노드의 키 값이 항상 자식 노드의 키 값보다 크거나 같음을 의미합니다.
2. 완전 이진트리(Complete Binary Tree) : 마지막 레벨을 제외한 모든 레벨은 꽉 차 있고, 마지막 레벨은 왼쪽부터 순서대로 채워져 있어야 합니다. 이 성질은 힙의 노드들을 가능한 한 균등하게 분포시키기 위함입니다

힙은 일반적으로 우선순위 큐(Priority Queue)를 구현하는 데에 사용되며, 자식 노드의 개수가 2개인 이진트리를 기반으로 합니다. 루트 노드는 우선순위가 가장 높은 요소를 나타내며, 우선순위가 높은 요소가 항상 루트에 위치합니다. 힙은 삽입, 삭제, 최소/최대값 검색 등의 연산을 \(O(log n)\)의 시간 복잡도로 처리할 수 있습니다.

 

배열을 사용한 Heap 구현

 

Fig. 1. Heap 배열 구현

Fig. 1 은 힙(Heap)을 배열(Array)을 사용하여 효율적으로 구현할 수 있다는 것을 보여줍니다. 배열을 사용하여 힙을 표현하면, 노드들을 레벨 순서대로 배열에 저장할 수 있습니다.

이때 배열의 인덱스는 1부터 시작하며, 인덱스\( i\)에 위치한 노드의 왼쪽 자식 노드는 \(2i\), 오른쪽 자식 노드는 \(2i+1\)에 위치합니다. 또한, 인덱스 i에 위치한 노드의 부모 노드는 \(i/2\)에 위치합니다.

 

배열을 사용하여 힙을 구현하면, 노드들 사이의 연결 링크를 구현할 필요가 없어집니다. 따라서, 노드를 저장하기 위한 공간과 더불어 불필요한 포인터를 저장할 필요가 없어지므로, 메모리 사용량과 구현 복잡도를 줄일 수 있습니다.

배열을 사용한 힙 구현에서는, 삽입, 삭제, 최소/최대값 검색 등의 연산을 \(O(log n)\)의 시간 복잡도로 처리할 수 있습니다. 또한, 배열을 사용하여 구현하는 것이 이해하기 쉽고 간단하기 때문에, 프로그래밍 대회 등에서 자주 활용됩니다

---

 

PQ/ Heap 삽입과 삭제

 

heap 구조를 구현하기 위해서는 세가지 요소가 필요한데, heap, last 와 comp 라고 정의하겠습니다.

• heap: 거의 완전한 이진트리 구조를 가지며, 각 노드는 힙-순서 성질을 만족하는 키 값을 가지고 있는 데이터 구조입니다. 이진트리를 배열에 저장하여 구현합니다.
• last: 배열 표현에서 T의 마지막 노드를 가리키는 참조(reference)입니다.
• comp: 키 값들의 총 순서(total order)를 정의하는 비교 함수(comparator function)입니다. 이 함수는 미니 힙인 경우 작은 값을, 맥스 힙인 경우 큰 값을 루트 노드에 유지하기 위해 사용됩니다.

 

노드 1 삽입

Fig. 2. last 찾기

• 먼저 last가 가르키는 노드 z를 찾아서 노드 1을 삽입합니다.
• z 에 값이 존재한다면, z 를 노드 1의 내부노드로 변경합니다.
• 그리고 힙 - 순서를 유지하기위해 comp를 통해 검사합니다.

Fig. 3. 비교

• Fig. 3을 보면 minheap인걸 확인 할 수 있습니다.
• 하지만 노드 1이 루트 노드 2보다 값이 작기 때문에,
• 힙 순서 유지를 위해 1과 6의 위치를 바꾸고, 1과 2을 바꿔 줄 수 있습니다.
• 다음과 같이 진행했을때, 아래와 같은 결과를 얻을 수 있습니다.

Fig. 4. 결과

---

노드 2 삭제

Fig. 5. 루트 노드 삭제

자 그럼 다음과 같이 루트 노드 2를 삭제한다면 어떤 결과가 있을까요?

루트 2 값을 last 포인터가 가리키고 있던  7 값으로 변경하게 됩니다.

Fig. 6. 힙 순서 유지

• 루트 키를 마지막 노드의 키 값으로 대체한 후에는 힙-순서 성질이 깨질 수 있습니다.
• Downheap 알고리즘은 루트에서부터 아래쪽으로 내려가면서 키 7를 교환하여 힙-순서 성질을 복원합니다.
• Downheap은 7이 리프에 도달하거나, 자식 노드의 키(9)가 7보다 크거나 같은 노드에 도달했을 때 종료됩니다.

 

---