[자료구조] 힙(Heap)

힙 (Heap)

---

힙(Heap)은 반 정렬상태를 유지하는 완전 이진 트리(complete binary tree)로 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 완전 이진 트리의 속성에 따라 높이가 K일때 K-1 레벨까지 중간에 비어있는 곳 없이 노드가 꽉 차있으며 K레벨은 왼쪽부터 채워진다. 또한 힙은 중복된 값을 허용하여 ‘부모의 키 값이 자식의 키 값보가 크거나 같은’ 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는것이므로 전체를 정렬하지 않고, 큰 값이 상위레벨에 있고 작은 값이 하위레벨에 있다 정도의 느슨한 정렬 상태를 유지한다.

 

 

 

힙은 최대힙과 최소힙으로 분류되는데, 부모 노드의 키 값이 자식 노드보다 큰 경우를 최대힙, 부모 노드의 키 값이 자식 노드보다 작은 경우를 최소힙이라고 한다.

• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

 

 

힙을 저장하는 가장 효과적인 자료구조는 배열이다. 힙은 이진트리이므로 루트부터 차례대로 번호(index)를 붙일 수 있다. 또한 완전 이진트리이기 때문에 중간에 비어있는 요소가 없다. 이 번호를 그대로 index로 사용하여 배열로 저장하는 것이다. 각 노드에 접근하는 규칙을 맞추기 위해 index 0은 비워두고 index 1부터 사용한다.

• 부모 index = 자식 인덱스 / 2 (왼쪽 오른쪽 상관 없이 나누고 몫만 취하면 부모의 index가 나온다)
• 왼쪽 자식 index = 부모 index * 2
• 오른쪽 자식 index = 부모 index * 2 + 1

 

 

 

힙의 삽입 연산, O(log2 n)

 

1. 새 노드를 가장 마지막에 삽입한다.
2. 새 노드를 부모 노드들과 비교하여 정렬 우선순위에 따라 승진시킨다. 만약 최대힙의 경우 부모 노드가 새 노드보다 작다면 둘의 위치를 바꾸며 승진하는 과정이 계속된다.
3. 부모 노드가 새 노드보다 크거나 같다 승진을 중지한다.

 

힙의 삭제 연산, O(log2 n)

 

1. 루트 노드를 삭제한다. (우선순위가 가장 높은 노드였으므로 출력되는 것)
2. 빈 루트 노드 자리에 힙의 마지막 노드를 가져온다.
3. 노드를 자식 노드들과 비교하여 정렬 우선순위에 따라 강등시킨다. 만약 최대힙의 경우 부모 노드가 새 노드보다 크다면 둘의 위치를 교환하여 강등시키는 과정이 계속된다.
4. 자식 노드가 자신보다 작거나 같다면 강등을 중지한다.