힙 정렬

힙 트리 구조를 이용하는 정렬방법이다. O(N*logN)

루트 노드를 마지막 노드와 바꿔준 후 힙구조를 만든다.

이때 마지막 노드는 정렬이 이루어졌다고 판단하고 범위에서 제외시킨다.

해당 과정을 반복하면 정렬이 완료된다.

 

힙 (Heap) 이란?

최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진트리를 기반으로 하는 트리이다.

최대 힙은 부모 노드의 값이 자식 노드의 값보다 커야 한다. 최소 힙은 그 반대이다.

public class Main{
	// 힙 구조 만들기
	public static int[] makeHeap(int[] arr) {
		for(int i=1; i<arr.length; i++) {
			int n = i;
			do {
				// 부모노드
				int parent = (n-1) / 2;
				// 부모노드 값이 자식 값보다 작을때 swap
				if(arr[parent] < arr[n]) {
					int temp = arr[parent];
					arr[parent] = arr[n];
					arr[n] = temp;
				}
				n = parent;
			}while(n != 0);
		}
		
		for(int k=0; k<arr.length; k++) {
    		System.out.print(arr[k] + " ");
    	}
		System.out.println();
		
		return arr;
	}
	
	public static int[] heapSort(int[] arr) {
		// 크기를 줄여가며 반복적으로 힙을 구성
		for(int i=arr.length-1; i>=0; i--) {
			//가장 큰 값을 마지막 요소와 바꿔 줌 
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			int root = 0;
			int n = 1;
			do {
				for(int k=0; k<arr.length; k++) {
		    		System.out.print(arr[k] + " ");
		    	}
				System.out.println();
				// 자식 노드
				n = (2 * root) + 1;
				// 자식 중에 더 큰 값 찾기
				if(n < i-1 && arr[n] < arr[n+1]) {
					n++;
				}
				// 루트보다 자식이 더 크다면 swap
				if(n < i && arr[root] < arr[n]) {
					temp = arr[root];
					arr[root] = arr[n];
					arr[n] = temp;
				}
				root = n;
			}while(n < i);
		}
		return arr;
	}
    public static void main(String[] args) throws Exception {
    	int arr[] = {9, 3, 2, 1, 5, 6, 2, 7, 8};
    	
    	// 힙 구조 만들기
    	arr = makeHeap(arr);
    	
    	// 힙 정렬 수행
    	arr = heapSort(arr);
    }
}

===============================================================================
9 8 6 7 3 2 2 1 5  // 힙 구조
5 8 6 7 3 2 2 1 9  // 힙 정렬 수행
8 5 6 7 3 2 2 1 9 
8 7 6 5 3 2 2 1 9 
8 7 6 5 3 2 2 1 9 
1 7 6 5 3 2 2 8 9 
7 1 6 5 3 2 2 8 9 
7 5 6 1 3 2 2 8 9 
2 5 6 1 3 2 7 8 9 
6 5 2 1 3 2 7 8 9 
6 5 2 1 3 2 7 8 9 
2 5 2 1 3 6 7 8 9 
5 2 2 1 3 6 7 8 9 
5 3 2 1 2 6 7 8 9 
2 3 2 1 5 6 7 8 9 
3 2 2 1 5 6 7 8 9 
3 2 2 1 5 6 7 8 9 
1 2 2 3 5 6 7 8 9 
2 1 2 3 5 6 7 8 9 
2 1 2 3 5 6 7 8 9 
2 1 2 3 5 6 7 8 9 
1 2 2 3 5 6 7 8 9 
1 2 2 3 5 6 7 8 9