힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

  알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 네 번째로 정리할 정렬 알고리즘은 힙 정렬입니다.

 

힙 정렬이란?

힙 정렬은 완전 이진 트리 구조를 기반으로 한 선택 정렬의 변형입니다. 힙 정렬은 힙 자료구조를 사용하여 정렬을 수행합니다.

 

동작 원리

1. 힙 생성(Build Heap)
   • 배열을 최대 힙 또는 최소 힙의 형태로 변환합니다.
   • 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음
   • 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음
2. 정렬 과정
   • 힙의 루트 노드(최대 힙의 경우 가장 큰 값)를 배열의 끝으로 이동시킵니다.
   • 힙의 크기를 줄이고 다시 힙 소것ㅇ을 유지하도록 조정합니다.
   • 이 과정을 반복하여 정렬된 배열을 만듭니다.

예시

힙 만들기

힙	새로 추가된 요소	요소 교체
null	6
6	5
6, 5	3
6, 5, 3	1
6, 5, 3, 1	8
6, 5, 3, 1, 8		5, 8
6, 8, 3, 1, 5		6, 8
8, 6, 3, 1, 5	7
8, 6, 3, 1, 5, 7		3, 7
8, 6, 7, 1, 5, 3	2
8, 6, 7, 1, 5, 3, 2	4
8, 6, 7, 1, 5, 3, 2, 4		1, 4
8, 6, 7, 4, 5, 3, 2, 1

 

정렬

힙	요소 교체	요소 삭제	요소 정렬
8, 6, 7, 4, 5, 3, 2, 1	8, 1
1, 6, 7, 4, 5, 3, 2, 8		8
1, 6, 7, 4, 5, 3, 2	1, 7		8
7, 6, 1, 4, 5, 3, 2	1, 3		8
7, 6, 3, 4, 5, 1, 2	7, 2		8
2, 6, 3, 4, 5, 1, 7		7	8
2, 6, 3, 4, 5, 1	2, 6		7, 8
6, 2, 3, 4, 5, 1	2, 5		7, 8
6, 5, 3, 4, 2, 1	6, 1		7, 8
1, 5, 3, 4, 2, 6		6	7, 8
1, 5, 3, 4, 2	1, 5		6, 7, 8
5, 1, 3, 4, 2	1, 4		6, 7, 8
5, 4, 3, 1, 2	5, 2		6, 7, 8
2, 4, 3, 1, 5		5	6, 7, 8
2, 4, 3, 1	2, 4		5, 6, 7, 8
4, 2, 3, 1	4, 1		5, 6, 7, 8
1, 2, 3, 4		4	5, 6, 7, 8
1, 2, 3	1, 3		4, 5, 6, 7, 8
3, 2, 1	3, 1		4, 5, 6, 7, 8
1, 2, 3		3	4, 5, 6, 7, 8
1, 2	1, 2		3, 4, 5, 6, 7, 8
2, 1	2, 1		3, 4, 5, 6, 7, 8
1, 2		2	3, 4, 5, 6, 7, 8
1		1	2, 3, 4, 5, 6, 7, 8
			1, 2, 3, 4, 5, 6, 7,8

 

힙 정렬 자바 코드

public class HeapSort {

    // 힙 정렬 메서드
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 1. 배열을 최대 힙으로 변환
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 힙에서 요소를 하나씩 추출하여 정렬
        for (int i = n - 1; i > 0; i--) {
            // 루트(가장 큰 값)를 끝으로 이동
            swap(arr, 0, i);

            // 힙 크기를 줄이고 다시 힙 속성을 유지
            heapify(arr, i, 0);
        }
    }

    // 힙 속성을 유지하는 메서드
    public static 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가 루트가 아니면 교환하고 재귀적으로 heapify 수행
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    // 두 요소를 교환하는 메서드
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 배열 출력 메서드
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 메인 메서드
    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};

        System.out.println("정렬 전 배열:");
        printArray(arr);

        heapSort(arr); // 힙 정렬 수행

        System.out.println("정렬 후 배열:");
        printArray(arr);
    }
}

 

결과 화면