힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

개념

Heap Sort는 Heap를 이용한 정렬 방법입니다.

Heap

Heap는 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전이진트리를 기본으로한 자료구조입니다.

Heap의 종류로 최대힙과 최소힙이 있습니다.

최대힙이라면 부모노트의 키값보다 자식노드의 키값이 작다는 특징이 있습니다.

로직

최대 힙이나 최소 힙을 구성하여 정렬을 하는 방법

1. 정렬해야 할 n개의 데이터를 최대 힙또는 최소힙으로 구성
2. 힙의 root노드에서 값을 순서대로 추출한다.
   • root노드의 값을 heap을 구성하는 마지막 노드와 교환한뒤 힙의 크기를 1만큼 줄이는 방식

코드

HeapSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

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

        // maxHeap을 구성
        // n/2-1 : 부모노드의 인덱스를 기준으로 왼쪽(i*2+1) 오른쪽(i*2+2)
        // 즉 자식노드를 갖는 노트의 최대 개수부터
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i); // 일반 배열을 힙으로 구성
        }

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0); // 요소를 제거한 뒤 다시 최대힙을 구성
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        int p = i;
        int l = i * 2 + 1;
        int r = i * 2 + 2;

        // 왼쪽 자식노드
        if (l < n && arr[p] < arr[l])
            p = l;
        // 오른쪽 자식노드
        if (r < n && arr[p] < arr[r])
            p = r;

        // 부모노드 < 자식노드
        if (i != p) {
            swap(arr, p, i);
            heapify(arr, n, p);
        }
    }

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

console

정렬 전: [65, 83, 96, 81, 38, 48, 29, 45, 89, 51]
정렬 후: [29, 38, 45, 48, 51, 65, 81, 83, 89, 96]

시간복잡도

힙생성(heapify) 알고리즘의 시간 복잡도는 $O(logN)$

장점

1. 추가적인 메모리를 필요로 하지 않으면서 항상 $O(NlogN)$으로 빠른 편이다.

단점

1. 불안정 정렬이다.