힙 정렬(Heap sort)

 

1. 정의

 힙(heap)이란 ‘더미’ 또는 ‘쌓다’라는 의미로 기본적으로 이진트리의 구조를 가진다. 힙 트리(Heap Tree)를 정의하면 모든 노드가 자식보다 큰(또는 작은) Complete Binary Tree이며 그 종류는 두가지 이다. 

(1) Max Heap Tree : 모든 노드가 자식보다 큰 Complete Binary Tree
(2) Min Heap Tree : 모든 노드가 자식보다 작은 Complete Binary Tree

---

2. 배열을 이용한 트리 표현

 이진 트리는 연결 리스트로 표현할 수 있으나, 배열을 이용하면 보다 간단하게 구현할 수 있다. 

 

[그림1] 데이터 배열

 

그림1은 임의의 데이터 배열이다. 배열의 인덱스가 완전 이진 트리의 래밸 순서를 표현한다면 아래 그림2 처럼 표현할 수 있다. 또한 각 인덱스를 i 라고 했을 때, 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드는 아래 식과 같이 표현 가능하다. 

 

 (1) 부모 노드 : (i-1)/2

 (2) 왼쪽 자식 노드 : 2i + 1

 (3) 오른쪽 자식 노드 : 2i + 2

---

3. 힙 정렬

힙 정렬을 위해선 크게 두가지 과정이 필요하다. 주어진 데이터를 힙 트리로 구성하는 과정과 하나씩 최대 값을 제거하며 트리를 재구성하는 과정이다. 

 

 (1) 힙 트리 구성

 

[그림2] 그림1의 데이터를 트리로 표현한 그림 

 

 

위의 트리는 아직 힙 트리가 아니다.  Max Heap Tree를 구성과정은 아래와 같다. 먼저 트리의 노드를 래밸 순서(배열의 인덱스  순서)대로 체크하며, 부모노드 보다 데이터가 큰 자식 노드를 찾는다. 

 

 

데이터가 8인 노드가 추가 됬을 때, 부모 노드의 데이터 보다 값이 크므로 이는 힙 트리가 아니다. 

 

그러므로 부모 노드와 노드를 교환한다. 

교환 후에도 힙 트리 구조가 맞는지 체크하여, 아니라면 재귀적으로 부모노드와 노드를 계속 교환한다. 

이제 Max 힙 구조가 되었다. 

다음 노드인 7을 삽입 후, 마찬가지로 힙 트리 구조가 아니라면 부모 노드와 교환한다. 

 

 

4가 부모 노드 1보다 더 크므로 교환한다.

 

 

최종적으로 만들어진 힙 트리와 배열의 데이터는 위와 같다. 

 

(2) 힙 트리 재구성

 

이제 가장 최대 값을 가진 루트 노드부터 순서대로 제거한다. 

 

가장 큰 8을 트리의 마지막 노드인 1과 교환한다. 

 

검정색으로 칠해진 노드는 정렬이 끝난 데이터이다. 힙 트리 범주에 속하지 않는다고 보면 된다. 정렬 과정에서 추가 저장 공간을 만들지 않기 위한 방법이다. 빨간색 노드는 힙 트리 구조에서 이상이 발생한 노드이다. 

 

자식 노드 중 (6, 7)에서 가장 큰 값을 가진 노드와 교환한다. 

 

마찬가지로 힙 트리 구조를 만들기 위해 교환한다. 

8이 정렬된 힙 트리 구조이다. 반복적으로 수행한다. 

가장 큰 값인 7을 가장 마지막 노드와 교환한다.

2의 자식 노드 6이 더 크므로 교환해야 한다. 지금까지 과정을 반복하여 수행한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

최종적으로 정렬된 형태이다.