힙 (Heap)

힙은 특정한 규칙을 만족하도록 구성된 이진 트리입니다. 이를 사용하면 최대[최소] 원소들을 log(N)의 복잡도로 찾아낼 수 있습니다.

 

규칙

- 힙의 대소 관계

- 힙의 모양 규칙

 

힙의 대소 관계

힙의 대소 관계는 부모 자식 관계에만 적용됩니다. 형제 간의 대소 관계는 신경쓰지 않습니다. 

이 규칙으로 인해 항상 최대[최소] 원소가 루트에 위치하기 때문에 빨리 찾아낼 수 있습니다.

 

힙의 모양 규칙

모양 규칙에는 두 가지가 있습니다

 

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.

2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

 

이 두 가지의 모양 규칙이 만족하면 노드의 개수만으로 트리의 모양이 정해지기 때문에 1차원 배열로 트리를 표현할 수 있습니다.

(루트가 0으로 시작하는 경우 왼쪽 자식은 2n+1, 오른쪽 자식은 2n+2 가 됩니다.)

 

새 원소의 삽입

 

힙은 모양 규칙을 엄격하게 지키기 때문에 원소를 추가할 때 크기에 상관없이 채울 수 있는 노드의 가장 왼쪽부터 채워나갑니다.

그러고 나서 노드의 부모와 값을 비교해가면서 위의 종결조건에 도달할 때까지 값을 부모와 바꿔나갑니다. 

이 경우 시간 복잡도는 log(N)이 됩니다.

 

최대 원소 꺼내기

 

최대 원소를 꺼낼 때 단순히 루트 노드의 값을 읽고 제거해버리면 다시 트리 구조를 재배열 해야 됩니다.

그보다는 간단한 방법으로 힙에서는 마지막 노드를 제거하고 값을 루트에 복사합니다. 그리고 루트에 복사한 값을 자식 노드들과 비교하면서 재배열합니다. 마찬가지로 시간 복잡도는 log(N)이 됩니다.

 

아래는 백준 예제를 풀면서 구현한 힙 코드 입니다.

 

백준 : 최소힙

백준 : 최대힙