힙 정렬 (Heap Sort)

1. 개요

• 완전이진트리를 기반으로 하는 정렬 알고리즘이다.
• 최대 힙을 구성한 후, 최대값을 차례대로 뽑으면서 정렬한다.
• 퀵 정렬과 병합 정렬의 성능이 더 좋아서 자주 사용되지는 않는다.

---

2. 특징

• 불안정 정렬이다.
• 시간복잡도: O(NLogN)

---

3. 코드

import java.util.Arrays;

public class HeapSortTest {

    public static void main(String[] args) {
        int[] nums = {3, 2, 7, 5, 11, 12, 1};

        heapSort(nums);

        System.out.println(Arrays.toString(nums));
    }

    private static 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--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int size, int i) {
        int parent = i;
        int leftChild = i * 2 + 1;
        int rightChild = i * 2 + 2;

        if (leftChild < size && arr[parent] < arr[leftChild]) {
            parent = leftChild;
        }
        if (rightChild < size && arr[parent] < arr[rightChild]) {
            parent = rightChild;
        }

        if (i != parent) {
            swap(arr, parent, i);
            heapify(arr, size, parent);
        }
    }

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