지난 글 : [알고리즘/Do it 알고리즘] - 병합 정렬
힙 알아보기
힙 정렬(heap sort)은 힙(heap)을 사용해 정렬하는 알고리즘으로, '부못값이 자식값보다 항상 크다'라는 조건을 만족하는 완전 이진 트리다. 또, '가장 큰 값이 루트에 위치'하는 특징을 이용하며 구체적으로 아래와 같은 작업을 반복한다.
- 힙에서 가장 큰 값인 루트를 꺼낸다.
- 루트 이외의 부분을 힙으로 만든다.이 과정에서 꺼낸 값을 늘어놓으면 배열은 정렬을 마치게 된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘으로, 힙에서 가장 큰 값인 루트를 거낸 뒤 남은 요소에서 다시 가장 큰 값을 구해야 한다. 만약 힙으로 구성된 10개의 요소에서 가장 큰 값(루트)을 없애면 나머지 9개 요소 중 가장 큰 값을 루트로 정해야 한다. 따라서 나머지 9개의 요소로 구성된 트리도 힙이 되도록 재구성해야 한다. 그 과정은 위 참고 링크에 나와있다.
배열을 힙으로 만들기
아래와 같은 이진트리가 있다.
여기서 4를 루트로 하는 부분트리(a)는 힙이 아니다. 그러나 왼쪽 자식 8을 루트로 하는 부분트리(b)와 오른쪽 자식 5를 루트로 하는 부분트리(c)는 모두 힙이다. 여기서 위 참고 링크에 나오는 방법을 사용해 루트 4를 알맞은 위치로 내려보내며 부분트리 (a)를 힙으로 만들 수 있다. 그 방법을 사용하면 아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙으로 만들 수 있다.
아래는 이 내용을 나타낸 것이다. 가장 아랫부분의 오른쪽 부분트리부터 시작해 왼쪽으로 진행하며 힙으로 만든다. 가장 아랫부분의 단계가 끝나면 하나 위쪽으로 부분트리 범위를 확장하고 다시 왼쪽으로 진행하며 부분트리를 힙으로 만든다.
a)
마지막(가장 아랫부분의 가장 오른쪽) 부분트리인 {9, 10}을 선택해 요소 9를 내려 힙으로 만든다.
b)
바로 왼쪽의 부분트리 {7, 6, 8}을 선택한다. 요소 7을 오른쪽으로 내려 힙으로 만든다.
c)
가장 아랫부분의 단계가 끝났으므로 부분트리의 선택 범위를 위로 한 칸 확장해 마지막(가장 오른쪽) 부분트리인 {5, 2, 4}를 택한다. 이미 힙이므로 옮길 필요가 없다.(우연히 힙인 상태)
d)
바로 왼쪽에 있는 3을 루트로 하는 부분트리를 택한다. 여기서는 요소 3을 오른쪽 아래로 내려 힙으로 만든다.
e)
부분트리의 선택 범위를 위로 한 칸 확장해 트리 전체를 선택한다. 왼쪽에 있는 자식 10을 루트로 하는 부분트리와 오른쪽에 있는 자식 5를 루트로 하는 부분트리는 모두 힙이다. 그러므로 요소 1을 알맞은 위치로 내려보내 힙으로 만들고 끝낸다.
아래는 힙 정렬을 수행하는 프로그램이다.
downHeap 메서드
배열 a에서 a[left] ~ a[right]의 요소를 힙으로 만드는 메서드다. 맨 앞에 있는 a[left[ 이외에는 모두 힙 상태라 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다.
heapSort 메서드
요솟수가 n개인 배열 a를 힙 정렬하는 메서드다. 아래와 같이 2단계로 구성된다.
1. downHeap 메서드를 사용해 배열 a를 힙으로 만든다.
2. 루트(a[0])에 있는 가장 큰 값을 꺼내 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는
과정을 반복해 정렬을 수행한다.
참고 서적 :
