# νž™ μ •λ ¬(Heap Sort)



μ™„μ „ 이진 트리λ₯Ό 기본으둜 ν•˜λŠ” νž™(Heap) 자료ꡬ쑰λ₯Ό κΈ°λ°˜μœΌλ‘œν•œ μ •λ ¬ 방식

μ™„μ „ 이진 νŠΈλ¦¬λž€?

μ‚½μž…ν•  λ•Œ μ™Όμͺ½λΆ€ν„° μ°¨λ‘€λŒ€λ‘œ μΆ”κ°€ν•˜λŠ” 이진 트리

νž™ μ†ŒνŠΈλŠ” λΆˆμ•ˆμ • 정렬에 속함

μ‹œκ°„λ³΅μž‘λ„

평균 μ΅œμ„  μ΅œμ•…
Θ(nlogn) Ω(nlogn) O(nlogn)

# κ³Όμ •

  1. μ΅œλŒ€ νž™μ„ ꡬ성
  2. ν˜„μž¬ νž™ λ£¨νŠΈλŠ” κ°€μž₯ 큰 값이 μ‘΄μž¬ν•¨. 루트의 값을 λ§ˆμ§€λ§‰ μš”μ†Œμ™€ λ°”κΎΌ ν›„, νž™μ˜ μ‚¬μ΄μ¦ˆ ν•˜λ‚˜ μ€„μž„
  3. νž™μ˜ μ‚¬μ΄μ¦ˆκ°€ 1보닀 크면 μœ„ κ³Όμ • 반볡

루트λ₯Ό λ§ˆμ§€λ§‰ λ…Έλ“œλ‘œ λŒ€μ²΄ (11 β†’ 4), λ‹€μ‹œ μ΅œλŒ€ νž™ ꡬ성

이와 같은 λ°©μ‹μœΌλ‘œ μ΅œλŒ€ 값을 ν•˜λ‚˜μ”© λ½‘μ•„λ‚΄λ©΄μ„œ μ •λ ¬ν•˜λŠ” 것이 νž™ μ†ŒνŠΈ

public void heapSort(int[] array) {
    int n = array.length;
    
    // max heap μ΄ˆκΈ°ν™”
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    
    // extract μ—°μ‚°
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

# 1번째 heapify

일반 배열을 νž™μœΌλ‘œ κ΅¬μ„±ν•˜λŠ” μ—­ν• 

μžμ‹λ…Έλ“œλ‘œλΆ€ν„° λΆ€λͺ¨λ…Έλ“œ 비ꡐ

  • n/2-1λΆ€ν„° 0κΉŒμ§€ μΈλ±μŠ€κ°€ λ„λŠ” μ΄μœ λŠ”?

    λΆ€λͺ¨ λ…Έλ“œμ˜ 인덱슀λ₯Ό κΈ°μ€€μœΌλ‘œ μ™Όμͺ½ μžμ‹λ…Έλ“œ (i2 + 1), 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œ(i2 + 2)이기 λ•Œλ¬Έ

# 2번째 heapify

μš”μ†Œκ°€ ν•˜λ‚˜ 제거된 이후에 λ‹€μ‹œ μ΅œλŒ€ νž™μ„ κ΅¬μ„±ν•˜κΈ° μœ„ν•¨

루트λ₯Ό κΈ°μ€€μœΌλ‘œ 진행(extract μ—°μ‚° 처리λ₯Ό μœ„ν•΄)

public 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(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

λ‹€μ‹œ μ΅œλŒ€ νž™μ„ ꡬ성할 λ•ŒκΉŒμ§€ λΆ€λͺ¨ λ…Έλ“œμ™€ μžμ‹ λ…Έλ“œλ₯Ό swapν•˜λ©° μž¬κ·€ 진행

퀡정렬과 ν•©λ³‘μ •λ ¬μ˜ μ„±λŠ₯이 μ’‹κΈ° λ•Œλ¬Έμ— νž™ μ •λ ¬μ˜ μ‚¬μš©λΉˆλ„κ°€ λ†’μ§€λŠ” μ•ŠμŒ.

ν•˜μ§€λ§Œ νž™ μžλ£Œκ΅¬μ‘°κ°€ 많이 ν™œμš©λ˜κ³  있으며, μ΄λ•Œ ν•¨κ»˜ λ”°λΌμ˜€λŠ” κ°œλ…μ΄ νž™ μ†ŒνŠΈ

# νž™ μ†ŒνŠΈκ°€ μœ μš©ν•  λ•Œ

  • κ°€μž₯ ν¬κ±°λ‚˜ κ°€μž₯ μž‘μ€ 값을 ꡬ할 λ•Œ

    μ΅œμ†Œ νž™ or μ΅œλŒ€ νž™μ˜ 루트 값이기 λ•Œλ¬Έμ— ν•œλ²ˆμ˜ νž™ ꡬ성을 톡해 κ΅¬ν•˜λŠ” 것이 κ°€λŠ₯

  • μ΅œλŒ€ k 만큼 떨어진 μš”μ†Œλ“€μ„ μ •λ ¬ν•  λ•Œ

    μ‚½μž…μ •λ ¬λ³΄λ‹€ λ”μš± κ°œμ„ λœ κ²°κ³Όλ₯Ό μ–»μ–΄λ‚Ό 수 있음

# 전체 μ†ŒμŠ€ μ½”λ“œ

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
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 (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}
μ΅œμ’… μˆ˜μ • : 11/15/2021, 1:31:19 PM