[Algorithm] 정렬 - Heap Sort (힙 정렬)

Heap Sort

• Heap 자료구조를 이용하여 정렬하는 방식
• Best case, Worst case 모두 시간 복잡도가 \(O(nlogn)\)
  • 그러나 대체로 Quick Sort보다 느림
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬

• 

 

Heap (약식)

• 최댓/최솟값을 찾는 연산을 빠르게 하기위해 고안된 자료구조
• 완전 이진트리(Complete Binary Tree)
• 부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높음
• index i에 대해서
  • 왼쪽 자식 노드의 index: \(i * 2 + 1\)
  • 오른쪽 자식 노드의 index: \(i * 2 + 2\)
  • 부모 노드의 index: \(i / 2\)
• 구조적으로 Tree이지만 배열로 표현가능
  •  

    

 

 

동작

Step 1. 배열을 Heap으로 만든다.

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높다

Step 1-1. 

Step 1-2.

Step 1-3.

 

 

 

Step 2. 첫번째 index와 마지막 index를 swap 후 heap size를 1 줄인다.

Step 2-1.

Step 2-2.

Step 2-3.

Step 2-4.

Step 2-5.

Step 2-6.

 

 

 

코드

public class Sort {
	
    public void heapSort(int[] arr) {
    	int lastIndex = arr.length - 1;
        buildHeap(arr, lastIndex);
        
        for(int i = lastIndex; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i-1);
        }
    }
    
    public void buildHeap(int[] arr, int lastIndex) {
    	int parent = (lastIndex - 1) / 2;
        
        for(int i = parent; i >= 0; i--) {
            heapify(arr, i, lastIndex);
        }
    }
    
    public void heapify(int[] arr, int parentIndex, int lastIndex) {
    	int leftChildIndex = parentIndex * 2 + 1;
        int rightChildIndex = parentIndex * 2 + 2;
        int largestIndex = parentIndex;
        
        if(leftChildIndex > lastIndex) {
        	return;
        }
        
        if(arr[leftChildIndex] > arr[largestIndex]) {
        	largestIndex = leftChildIndex;
        }
        
        if(rightChildIndex < lastIndex && arr[rightChildIndex] > arr[largestIndex]) {
        	largestIndex = rightChildIndex;
        }
        
        if(largestIndex != parentIndex) {
        	swap(arr, largestIndex, parentIndex);
            heapify(arr, largestIndex, lastIndex);
        }
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

 

왜 \(O(nlogn)\)일까?

Heap Sort의 의사코드를 보면 다음과 같다.

HeapSort(arr) {

    buildHeap(arr) // O(n)
    
    // O(nlogn)
    for( i = heapLastIndex ~ 0 ) {
        swap(arr, i, heapLastIndex)
        heapify(arr, 0, i - 1)
    }
}

Build Heap이 \(O(n)\)인 이유

 

for 구문이 \(O(nlogn)\)인 이유