[알고리즘_개념] 힙 정렬, Heap Sort

힙정렬 알고리즘은 

입력받은 숫자를 최대 혹은 최소 힙 구조로 만들고 현재 값 중에 가장 큰값 혹은 작은 값을 루트로부터 추출하여 큰값부터 차례대로 뽑아 정렬문제를 해결하는 알고리즘이다.

 

아래 동영상이 도움이 많이 됐다아ㅏ.!!!

LOGIC

1. 배열에 담기

2. max-heapify

3. 1번노드와 마지막 노드 exchange

4. 마지막 노드를 arraylist에 따로 담기, heap크기 = heap크기 -1

 

  

 

 

package data_structure;

import java.util.ArrayList;

// max heap!
public class HeapSort {
    static ArrayList<Integer> sortArr = new ArrayList<>();
    static int[] swap(int[] a, int m, int n){
        int tmp = 0;

        tmp = a[m];
        a[m] = a[n];
        a[n] = tmp;

        return a;
    }

    static int[] maxHeapify(int[] a){
        int start = a.length/2;
        for(int i=start; i>=1; i--){
            //System.out.println(2*i + " " + (2*i+1));
            if(2*i < a.length && a[i] <= a[2*i]) { a = swap(a, i, 2*i); }
            if((2*i)+1 < a.length && a[i] <= a[(2*i)+1]) {
                a = swap(a, i, (2*i)+1);
            }
        }
        return a;
    }

    static int[] exchange_1_n(int[] a){
        int arrLength = a.length-1;

        a = swap(a, 1, arrLength);
        sortArr.add(a[arrLength]);

        int[] noneMaxHeap = new int[arrLength];

        for(int i=1; i<arrLength; i++){
            noneMaxHeap[i] = a[i];
        }

        return noneMaxHeap;
    }

    public static void main(String[] args) {
        int[] a = {0, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1};

        for(int ai : a){
          System.out.print(ai + " ");
        }
        System.out.println();

        int end = a.length-1;

        for(int i=0; i<end; i++){
            a = maxHeapify(a);
            a = exchange_1_n(a);
        }
        
        System.out.println(sortArr);
    }
}

 

 

 

[REFERENCE]

https://www.youtube.com/watch?v=ehNVf2Bcm2Q

https://www.youtube.com/watch?v=S42s_ANn4c4