[알고리즘 개념] 힙 (heap)

 

이진트리

 

: 모든 노드의 자식 노드가 2개 이하인 트리 구조

 

출처 : https://m.blog.naver.com/ndb796/221228342808

 

 

완전 이진트리

 

이진트리와 다르게 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽, 오른쪽 자식 노드 순서로 쌓이게 되는 트리를 말한다. 

이진트리는 중간에 노드가 비어있을 수 있지만, 완전 이진 트리는 중간 노드가 비어있을 수 없는 형태이다.

 

 

힙

 

힙은 최대 힙과 최소 힙이 있다. 

최대 힙은 구성하는 모든 노드가 '부모 노드가 자식 노드보다 크다'라는 규칙을 가진 것이다.

최소 힙은 반대로 구성하는 모든 노드에 대해 부모 노드가 자식 노드보다 작다는 규칙을 가진 것이다.

 

따라서 힙의 루트는 최댓값이나 최솟값이다. 따라서 힙은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료 구조이다.

 

배열의 인덱스를 활용하여 자식 노드와 부모 노드를 찾기 쉽기 때문에 힙은 보통 배열로 구현한다.

루트의 인덱스를 1로 하였을 때, 아래의 관계를 만족한다.

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

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

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

 

완전 이진트리를 힙의 구조로 바꾸는 알고리즘이 힙 생성 알고리즘이다.

힙 생성 알고리즘은 반복된 힙의 삽입 연산이다.

루트 노드에서부터 마지막 노드까지 추가하며 힙 삽입 연산을 한다.

 

 

힙의 삽입

 

힙에 새로운 노드가 추가된 경우이다.

새로운 노드를 마지막 노드에 이어서 삽입하여, 부모 노드들과 비교하며 힙의 성질을 만족시킨다.

 

 

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

 

힙의 삭제

 

힙에서의 삭제는 루트 노드의 삭제를 의미한다.

즉, 최대 힙에서 삭제는 최댓값의 삭제와 같다.

힙의 삭제는 루트 노드를 삭제 후, 마지막 노드를 빈 루트 자리에 삽입한다.

이후 알맞은 위치를 찾아 내려가면 된다.

 

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

 

힙 정렬

 

힙 배열은 정렬되어 있지 않은 배열이다.

힙을 내림차순 혹은 오름차순으로 정렬하기 위해선 힙의 삭제 연산을 이용하면 된다.

 

최대 힙을 내림차순으로 정렬해보자.

루트 노드와 마지막 노드를 교환한다. 교환된 마지막 노드를 제외한 나머지 노드 간의 최대 힙을 만족시킨다.

이 과정을 반복하여 내림차순으로 정렬하면 된다.

 

힙의 삽입, 삭제 연산의 시간 복잡도는 힙 트리의 높이와 노드의 개수에 비례한다.

노드가 n개일 때 힙 트리의 높이는 log2(n)이므로 시간 복잡도는 O(n*log2(n))이다.

 

따라서 힙 정렬은 구현하기에는 복잡하지만 효율적인 정렬 방식이라 할 수 있다.