[Algorithm] 정렬 - 힙정렬(Heap Sort)

#요약

• 2023.11.20 - [Computer Science/Data Structure] - [Data Structure] 비선형 - 힙(Heap)
• 최대 힙, 최소 힙 트리를 구성하여 정렬하는 방법
• 내림차순 정렬 ➡️ 최대 힙 구성
• 오름차순 정렬 ➡️ 최소 힙 구성

[Data Structure] 비선형 - 힙(Heap)

#구체적 설명

1. 정렬해야할 n개의 요소들로 최대 힙(내림차순 정렬을 위해)을 만든다.
   • 최대 힙(max heap): 부모 노드의 key가 자식노드 key보다 크거나 같은 완전 이진 트리
     ➡️ 즉, 루트의 노드가 가장 큰 값을 가진다.
2. 그 다음으로 루트 노드에서 하나씩 힙에서 데이터를 꺼내 배열의 뒤부터 저장한다.
   • 이 과정을 heapify 라고 부름
     ➡️ 루트 노드를 제외하면 루트 노드가 사라지기때문에 말단의 오른쪽의 leaf 노드를 채워 넣는다.
     ➡️ 가장 작은 값이 와서 다시 최대 힙을 만들기 위해서 자식 노드 중 값이 큰 자식 노드들을 swap 한다.
     ➡️ 다시 최하단 leaf 노드에 위치하도록한다.

#알고리즘

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

#코드 작성

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 heapSort(int[] array) {
    int n = array.length;
 
    // max heap을 만든다.
    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 (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 

 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

//https://gyoogle.dev/blog/algorithm/Heap%20Sort.html

#결과

10, 20,40, 60, 220, 230, 550

#시간복잡도

최선	O(nlogn)
평균	O(nlogn)
최악	O(nlogn)

#장단점

장점	단점
- 최선, 평균, 최악 모두 O(nlogn)이라는 시간복잡도	- 구현이 복잡하다.

#참고

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

https://gyoogle.dev/blog/algorithm/Heap%20Sort.html

힙 정렬(Heap Sort) | 👨🏻‍💻 Tech Interview

힙 정렬(Heap Sort)