힙 정렬
힙 정렬은 선택 정렬을 응용한 알고리즘으로 힙의 특성을 이용한 정렬입니다.
힙 : 부모값이 자식값보다 항상 크다(작다)라는 조건을 만족하는 완전이진트리, 힙에 루트는 항상 모든 수 중 가장 큰 값이 위치한다.
트리
root(루트) : 트리에 가장 상위부분
parent(부모), child(자식) : 트리에서 요소의 상하 관계
sibling(형제) : 자식 간의 관계
완전이진트리 : 트리의 한 종류
완전 : 부모가 자식을 왼쪽부터 추가하는 모양을 유지
이진 : 부모가 가질 수 있는 자식의 수가 최대 2개이다.
힙
- 트리의 한 종류이다.
- 항상 완전이진트리의 형태를 가져야한다.
- 힙에서 부모와 자식 사이의 대소관계는 일정하나 형제 간의 대소관계는 일정하지 않을 수 있다.
- 여기서 일정하다라는 것은 상대적으로 크거나 작거나를 뜻한다.
- 위와같이 힙은 형제간의 대소관계가 일정하지 않기에 '부분순서트리'라고도 한다.
힙의 경우 항상 루트가 가장 큰 값이 와야하며 루트를 중심으로 이진트리형태로 좌측부터 값이 채우진다. 이때 부모와 자식간에는 항상 대소관계가 일정하게 유지 되어야하며, 형제간에는 대소관계가 유지되지 않을 수 있다.
힙은 부모와 자식의 인덱스 사이 다음과 같은 관계가 성립한다
- 부모는 a[ (i - 1) /2 ] -> 자신의 부모위치
- 왼쪽 자식 a[ i * 2 + 1] -> 자신의 자식위치
- 오른쪽 자식 a[ i * 2 + 2] -> 자신의 자식위치
힙 정렬
다음과 같은 과정을 반복하면서 정렬을 수행한다.
- 현재 힙에서 가장 큰 값인 Root값을 꺼낸다.
- 힙에서 가장 마지막 요소를 루트로 이동시킨다
- 자식과 비교하며 위치를 이동시킨다. 이때, 자식과 변경이 일어나지 않거나 잎에 다다르면 끝이난다.
배열을 힙으로 만들기
이 부분은 이해를 돕기 위해서 그림을 첨부합니다.
위 그림과 같이 부분트리들을 오른쪽부터하여 힙으로 만들어갑니다. 이때 부모,자식의 요소위치를 어떻게 계산하는지는 위에서 설명했습니다. 그렇다면 실제 어떻게 구현하는지 코드를 작성해보겠습니다.
//교환부분
static void swap(int[] a ,int idx1, int idx2){
int t = a[idx1]; a[idx1] = a[idx2] ; a[idx2] = t;
}
//힙 만들기
static void downHeap(int[] a , int left , int right){
int tmp = a[left];
int child ;
int parent ;
for(parent = left ; parent < (right + 1) / 2 ; parent = child){
int cl = parent * 2 + 1; // 왼쪽 자식
int cr = cl + 1; // 오른쪽 자식
child = (cr <= right && a[cr] > a[cl]) ? cr: cl;
if(tmp >= a[child])
break;
a[parent] = a[child];
}
a[parent] = tmp;
}
//정렬
static void heapSort(int[] a, int n){
//초기 힙 만드는 작업
for(int i = (n-1)/2 ; i >= 0 ; i--)
downHeap(a , i , n-1);
//힙 정렬
for(int i = n - 1 ; i > 0 ; i--) {
swap(a, 0, i);
downHeap(a, 0, i - 1);
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("힙 정렬");
System.out.print("요솟수 : ");
int nx = s.nextInt();
int[] x = new int[nx];
for(int i = 0 ; i < nx ; i++){
System.out.print("x[" + i + "] : ");
x[i] = s.nextInt();
}
heapSort(x,nx);
System.out.println("오름차순 정렬");
for(int i = 0 ; i < nx ; i++)
System.out.print(x[i] + " ");
}코드를 볼 때 기존에 부모-자식관계에 규칙을 적어놓은 상단에 내용을 생각하면서 보면 쉽게 이해할 수 있을 것이다.
예를들어 {5,3,7,6,9,1,2}라는 크기 7 배열이 있다고 가정하면 n = 7이다. 아래와 같이 위치하게 된다.
여기서 보면 최종적으로 루트를 중심으로 2개씩 뻗어나가기에 요소수가 홀수면 최종적으로 하나의 부모에서 좌우가 채워진 상태로 끝이나고 짝수라면 왼쪽만 채워지고 끝날 것이다. 그리고 한 가지는 부모와 자식사이에 어떤한 규칙이 있는지 위에서 설명했듯이, 부모요소는 자식요소 위치인 i에 대해서 (i - 1) /2인 위치에 존재한다. 이를 활용하면 결국 n - 1은 마지막 요소가 있는 위치이며 /2를 해주면 부모 위치가 된다. 이렇게 마지막 부분트리부터 해서 찾아나가면 최종적으로 루트까지 도달하게된다. 그리고 힙을 만드는 부분에서는 부모와 자식 값들을 비교하면서 부모의 값을 변경시켜나간다.
그리고 초기에 힙을 만들고나서는 가장 큰 값이 루트에 있기에 이 값을 배열의 마지막으로 교환해주고 다시 부분 힙을 만들기 위해서 크기를 1씩 줄여나가면서 수행하면 된다.