힙 정렬(Heap Sort)

한유진·2021년 10월 24일

Heap Sort 알고리즘 정렬 알고리즘 힙 정렬

알고리즘

목록 보기

5/8

정의

힙 : 최소값 또는 최대값을 빠르게 찾아내기 위한 완전이진트리 형태로 만들어진 자료구조
노드는 항상 우선순위가 높은 노드 == 최대값과 최소값을 빠르게 찾을 수 있다. (시간복잡도 : O(1))

최소 힙 : 각 노드의 값은 자기 자식의 값보다 작다
최대 힙 : 각 노드의 값은 자기 자식의 값보다 크다

-힙 구조는 반 정렬 상태이지 완전 정렬상태가 아니다! 힙 구조 + 정렬하는 과정

정렬 방법

초기상태 ==> 최대힙 ==> 정렬

최대 힙 만들기 (heapify)
정렬하기

코드

재귀 (Top-Down 형식)

public static void sort(int[] a) {
	sort(a,a.length);
}
private static void sort(int[] a, int size) {
	//원소가 1개이거나 0개일 경우 정렬할 필요가 없으므로 함수를 종료
	if (size < 2) return;
    
    //가장 마지막 요소의 부모 인덱스
    int parentIdx = getParent(size - 1);
    
    //최대힙 구성
    for(int i = parentIdx; i >= 0; i--) {
    	heapify(a, i, size - 1);
    }
    
    //root인 0번째인덱스와 i번째 인덱스의 값을 교환해준 뒤
    //0 ~ (i - 1)까지의 부분트리에 대해 max heap을 만족하도록 재구성
    for (int i = size - 1; i > 0; i--) {
    	swap(a, 0, i);
        heapify(a, 0, i - 1);
        //heapify하면 index : 0값에는 (0~i-1)값의 최대값이 있음
    }
}

//부모 인덱스를 얻는 함수
private static int getParent(int child) {
	return (child - 1) / 2;
}

//두 인덱스의 원소를 교환하는 함수
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

//힙을 재구성하는 함수
private static void heapify(int[] a, int parentIdx, int lastIdx) {
	
    //현재 트리에서 부모 노드의 자식노드 인덱스를 각각 구해준다.
    //현재 부모 인덱스를 가장 큰 값을 갖고있다고 가정한다.
    
    int leftChildIdx = 2 * parentIdx + 1;
    int rightChildIdx = 2 * parentIdx + 2;
    int largestIdx = parentIdx;
    
    //자식노드 인덱스가 트리의 크기를 넘어가지 않으면서, 현재 가장 큰 인덱스보다 왼쪽 자식노드의 값이 더 클경우, 가장 큰 인덱스를 가리키는 largestIdx를 왼쪽 자식노드 인덱스로 바꿔준다.
   	if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
    	largestIdx = leftChildIdx;
    }
    //자식 노드 인덱스가 트리의 크기를 넘어가지 않으면서, 현재 가장 큰 인덱스보다 오른쪽쪽 자식노드의 값이 더 클경우, 가장 큰 인덱스를 가리키는 largestIdx를 오른쪽 자식 노드인덱스로 바꿔준다.
    if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
    largestIdx = rightChildIdx;
	}
    
    //largestIdx와 부모노드가 같지 않다는 것은
    //위 자식 노드 비교 과정에서 현재 부모노드보다 큰 노드가 존재한다는 뜻이다.
    //그럴 경우 해당 자식 노드와 부모노드를 교환해주고,
    //교환된 자식 노드를 부모노드로 삼은 서브트리를 검사하도록 재귀 호출한다.
    if(parentIdx != largestIdx) {
    	swap(a, largestIdx, parentIdx);
        heapify(a, largestIdx, lastIdx);
    }
}