힙 정렬

개요

최대 Heap 자료 구조를 이용해서 최대값을 pop하고 해당 값을 뒤부터 적재하며 정렬.

---

복잡도

	최악	평균	최소
Big O 표기법	O(nlogn)	O(nlogn)	O(nlogn)

---

알고리즘 절차

1. 모든 요소를 최대 heap 자료 구조로 만들 수 있도록 heapify 시킴.
2. 최대 heap 에서 pop을 하고 마지막 요소와 swap함. 이 과정을 모든 요소가 정렬이 되도록 계속 반복함.

---

자바 코드

class Heap {
    public static void main(String[] args) {
        int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543};

        heapSort(testCase1);

        for (int item : testCase1) {
            System.out.println(item);
        }
    }
    
    public static void heapSort(int[] array) {
        int n = array.length;

        for (int i = n/2-1; i>=0; i--){
            heapify(array, n, i);
        }

        for (int i = n-1; i>0; i--) {
            swap(array, 0, i); 
            heapify(array, i, 0);
        }
    }
    
    public static void heapify(int array[], int n, int i) {
        int p = i;
        int l = i*2 + 1;
        int r = i*2 + 2;

        if (l < n && array[p] < array[l]) {
            p = l;
        }
        if (r < n && array[p] < array[r]) {
            p = r;
        }

        if(p != i) {
            swap(array, p, i);
            heapify(array, n, p);
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}