[Algorithm] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 트리 구조 (Heap Tree Structure)를 이용하여 정렬하는 방법이다.

(최대힙 트리나 최소힙 트리를 사용한다.)

 

1. 내림차순일 경우 데이터를 최대힙으로 구성하고 오름차순일 경우 최소힙으로 구성한다.

2. 최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 삭제를 반복하면 다음 최대값이 루트노드가 되어 최종적으로 내림차순 정렬이 된다.

3. 반대로, 최소힙의 경우??

 

 

 

힙 정렬 (Heap Sort)의 시간 복잡도

힙 생성 알고리즘의 시간 복잡도는 O(log N)이다. 전체 데이터의 갯수가 N개이므로 시간 복잡도는 O(N * log N)이다.

 

힙 정렬 (Heap Sort)의 구현

import java.util.Arrays;
import java.util.Random;

public class HeapSort {

	static final int N = 10;
    
    public static void main(String[] args) {
    
    	Random random = new Random();
        
        int[] arr = new int[N];
        for(int i = 0; i < N; i++) {
        	arr[i] = random.nextInt(100);
		}
        
        System.out.println("정렬 전: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
    
    private static void heapSort(int[] arr) {
    	int n = arr.length;
        
        for(int i = n / 2 - 1; i >= 0; i--) {
        	heapify(arr, n, i);
        }
        
        for(int i = n - 1; i > 0; i--) {
        	swap(arr, 0, i);
            heapify(arr, i , 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
    	int p = i; 
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        
        // 왼쪽 자식노드
        if (l < n && arr[p] < arr[l])
        	p = l;
        // 오른쪽 자식노드
        if (r < n && arr[p] < arr[r]) 
        	p = r;
         
        // 부모노드 < 자식노드
        if (i < p) {
        	swap(arr, p, i);
            heapify(arr, n, p);
        }
     }
     
     private static void swap(int[] arr, int a, int b) {
     	int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
     }
}

 

 

 

출처

https://banjjak1.tistory.com/50

https://m.blog.naver.com/ndb796/221228342808

https://herong.tistory.com/entry/%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-Sort