[Algorithm] Heap 정렬

[2d3k]

힙정렬의 구현방식

공간복잡도, 시간복잡도

장단점

[2d3k]

1

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

        // 힙 구성
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 힙에서 요소 추출하여 정렬
        for (int i = n - 1; i > 0; i--) {
            // 현재 최대값(루트)을 마지막 요소와 교환
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 다시 힙 구성
            heapify(arr, i, 0);
        }
    }

    void heapify(int[] arr, int n, int i) {
        int largest = i; // 가장 큰 요소
        int left = 2 * i + 1; // 왼쪽 자식
        int right = 2 * i + 2; // 오른쪽 자식

        // 왼쪽 자식이 루트보다 크면 largest 갱신
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // 오른쪽 자식이 largest보다 크면 largest 갱신
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // largest가 루트가 아니면 교환 후 힙 구성
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    // 테스트를 위한 코드
    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

위 코드에서 heapSort 메소드가 힙정렬을 수행하는 메소드입니다. heapify 메소드는 주어진 노드를 루트로 하는 서브트리를 힙 구조로 만드는 메소드입니다. 테스트를 위해 main 메소드에서는 정렬할 배열을 생성하고 heapSort 메소드를 호출한 후 결과를 출력합니다.

2 힙정렬(Heap Sort)의 시간복잡도는 O(nlogn)입니다.

힙정렬의 공간복잡도는 O(1)입니다. 입력 배열 안에서 정렬을 수행하기 때문에, 추가적인 공간이 필요하지 않습니다.

이러한 시간복잡도와 공간복잡도는 힙정렬이 대부분의 상황에서 효율적인 정렬 알고리즘이라는 것을 보여줍니다.

3 힙(Heap) 자료구조는 이진트리 형태로 구현되어 있으며, 각 노드의 값이 자식 노드의 값보다 큰지 또는 작은지에 따라 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구분됩니다. 이러한 구조적 특성으로 인해 힙은 다음과 같은 장단점을 가집니다.

장점: 정렬, 우선순위 큐 등 다양한 알고리즘에서 활용될 수 있습니다. 최대값 또는 최소값을 빠르게 찾을 수 있습니다. 최대 힙에서는 루트 노드가 최대값이며, 최소 힙에서는 루트 노드가 최소값입니다. 삽입, 삭제 연산 모두 O(log n)의 시간 복잡도를 가지므로, 대량의 데이터를 처리할 때 효율적입니다.

단점: 일반적으로 배열을 기반으로 구현되기 때문에, 메모리 사용량이 큽니다. 힙은 이진트리 형태로 구현되어 있기 때문에, 노드의 추가, 삭제 등의 연산이 다른 자료구조에 비해 복잡합니다. 또한, 구현 방법에 따라 성능 차이가 크기 때문에, 구현 방법을 최적화해야 합니다.

[hyeonayou]

1. 힙정렬은 삽입보다는 삭제 과정만 이루어진다고 생각하면 편하다. 최대힙을 구현한 뒤, 루트 노드를 삭제하고 배열의 맨 마지막에 넣어주고, 깨진 힙을 재구조화 하는 과정을 반복하면 된다. 최대힙의 루트 노드를 배열의 마지막 값과 교환 -> 가장 큰 값은 배열의 마지막에 저장 .이것을 반복하면 됨.

2. 힙정렬(Heap Sort)은 힙(Heap) 자료구조를 이용한 정렬 알고리즘으로서, 시간 복잡도가 O(n log n)인 효율적인 알고리즘 중 하나이며 힙정렬은 안정성이 보장되지 않지만, 원본 배열을 바로 정렬하는 것이 아니라 별도의 힙 자료구조를 사용하기 때문에 공간 복잡도는 O(1)

3. 장점 : 항상 O(n log n)의 시간 복잡도를 보장 입력값에 영향을 받지 않는 불변성(immutable)을 가지고 있음. 원본 배열을 바로 정렬하는 것이 아니라 별도의 힙 자료구조를 사용하기 때문에 공간 복잡도가 O(1)

단점: 안정성이 보장되지 않음 다른 알고리즘들과 마찬가지로 최악의 경우에는 O(n^2)의 시간 복잡도를 가질 수 있음 캐시 지역성(cache locality)이 좋지 않아서 다른 알고리즘들보다 느릴 수 있음. 다른 정렬 알고리즘들과 마찬가지로 입력 배열의 크기가 작을 경우, 다른 알고리즘보다 느릴 수 있음