알고리즘을 위한 자료구조 - 힙(Heap)

 

힙(Heap)

 

힙(Heap)의 개념

 

 - 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조이다.

 

 - 여러 개의 값 중 최대, 최소를 빠르게 찾기 위해 만들어진 자료구조이다.

 

---

 

힙의 종류

 

 - 최대 힙(Max Heap)

   : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다. // Key(부모 노드) >= Key(자식 노드)

[ 최대 힙(Max Heap) ]

 

 - 최소 힙(Min Heap)

   : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다. // Key(부모 노드) <= Key(자식 노드)

[ 최소 힙(Min Heap) ]

 

---

 

힙의 구현

 

 - 힙의 데이터를 저장하는 자료구조는 배열을 이용한다.

 

 - 힙에서 부모 노드와 자식 노드는 특별한 관계를 가진다.

   왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) X 2

   오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) X 2 + 1

   부모 노드의 인덱스 = (자식 노드의 인덱스) / 2

 

---

 

힙의 삽입

 

 - 힙의 삽입 방법

   1. 힙에 새로운 노드는 힙의 마지막 노드에 이어서 삽입한다.

   2. 새로운 노드를 부모 노드들과 교환하여 힙의 성질(최대 힙, 최소 힙)을 만족시키도록 반복한다.

 

 - 힙의 삽입 예시(최대 힙)

 

 1. 힙의 초기 상태 

 2. 힙에 9 삽입 

 

3. 9와 9의 부모인 3이 힙의 성질을 만족하도록 위치를 변경한다. 

4. 9와 9의 부모인 7이 힙의 성질을 만족하도록 위치를 변경한다.

5. 9와 9의 부모인 11은 힙의 성질을 만족하므로 변경하지 않는다.

6. 9를 삽입 한 최종 모습

 

 

---

 

힙의 삭제

 

 - 힙의 삭제 방법

   1. 루트 노트를 삭제한다.

   2. 힙의 마지막 노드를 루트 노드로 가져간다.

   3. 루트 노드와 자식 노드들을 비교하며 힙의 성질을 만족시키도록 반복한다. 

 

 - 힙의 삭제 예시(최대 힙)

1. 힙의 초기 상태

 

2. 루트 노드 삭제 후 힙의 마지막 노드(3)를 루트 노드로 가져온다.

3. 힙의 성질을 만족하도록 부모 노드 3과 자식 노드들 9와 8 중 더 큰 값인 9와 위치를 변경한다.

4. 힙의 성질을 만족하도록 부모 노드 3과 자식 노드들 7과 6 중 더 큰 값인 7과 위치를 변경한다.

5. 부모 노드 3과 자식 노드 2는 힙의 성질을 만족하기 때문에 위치를 변경하지 않는다.

6. 힙 삭제 후 최종 모습