힙정렬 Heap Sort

정의

• 차순으로 정렬하는 방법 중 하나
• 이진트리를 기반한 데이터 스트럭처
• 정렬이 되는 트리에 넣고 그대로 출력하면 정렬이 됨.

알고리즘 순서

1. 이진트리의 맞는 위치에 받은 배열을 차례대로 넣음
2. 이진트리의 조건에 맞춰서 정리됨
3. 이트리의 조건에 맞춰서 출력하면 정렬됨

자바 코드

    public static void heapSort(int arr[]) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapTree(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapTree(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    public static void heapTree(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapTree(arr, n, largest);
        }
    }

*이 코드는 https://www.geeksforgeeks.org/heap-sort/ 에서 가져옴

평균 시간 복잡도 Avg. time complexity

$O(n, log, n)$

최악 시간 복잡도 Worst time complexity

$O(n, log, n)$

공간 복잡도 space complexity

$O(1)$

안정성 stability

no

계산법

순회 횟수

• 트리에서 확인해가며 위치를 찾을 때(입력) : $O(log, n)$
• 하나씩 방문해서 출력할 때(출력) : $O(n)$

$O(n) \cdot O(log\, n)=O(n\, log\, n)$