[Data Structure] 힙(Heap) 구조

일반적인 힙이라는 단어는, 메모리 구조에서 동적할당 시 할당되는 공간을 의미한다.

 

하지만 자료구조 힙의 경우, 힙 순서 속성을 만족하는 트리를 의미한다. 이런 힙은 우선순위 큐를 구현하기 위해 만들어진 자료구조이다.

 

여기서 힙 속성이란 두 가지 조건을 충족해야 하는데 다음과 같다.

 

1. 힙 구조는 항상 완전 이진 트리여야 한다.

 

2. 모든 노드는 자신의 부모 노드보다 크다.(우선순위가 후순위다)

 

이 두 조건을 충족하는 트리 구조가 바로 힙 구조이다. 2번 조건을 만족하기만 하면 되기 때문에 힙 구조는 항상 반정렬 상태(느슨한 정렬 상태)를 유지한다.

 

또한 힙 구조는 이진 탐색 트리가 아니기 때문에 중복된 값을 허용한다.

 

우선순위 큐를 구현하기 위해 만들어진 만큼, 우선순위가 큰 것이 우선이면 최대 힙, 작은 값이 우선이면 최소 힙으로 구분된다.

 

 

최대 힙 - 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

 

최소 힙 - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

힙 구조의 삽입 연산

 

데이터를 완전 이진 트리가 만족하는 공간에 노드를 추가 -> 이후 부모 노드의 값과 비교하여 크다면 그대로 두고, 작다면 부모 노드와 교체를 한다.

 

힙 구조의 삭제 연산

 

보통 힙 구조의 삭제는 최소값 삭제, 즉 루트 노드의 삭제를 의미한다.

 

루트 노드의 삭제 -> 현재 트리 내에서 최고 깊이, 최우측 노드를 루트 노드의 자리로 변경 -> 이후 값을 비교하여 올바른 위치로 값을 옮긴다. -> 힙 구조의 규칙을 위배하지 않을 때까지 값 교체 반복

 

 

힙 구조와 배열

 

힙 구조를 저장하는 표준적인 자료구조는 배열이다. 구현의 편의성을 위해 0번 인덱스는 비워두는 경향이 있으며 특정 노드의 자리는 절대 변하지 않는다. ex) 루트 노드의 오른쪽 자식 노드는 항상 3번(0번 인덱스가 비워진 경우)이다.

 

특정 노드의 자식 노드를 계산할 때는 2n, 2n + 1의 값(마찬가지로 0번 인덱스가 비워진 경우)을 찾으면 된다.