힙 정렬 (Heap Sort)

특징

• 힙 자료구조 형태의 정렬 방식
• 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행
• 자바에 있는 힙을 만들어서 값을 넣은 후에 사용해도 된다
• O(nlogn)

소스코드

• array를 heap으로 바꾸면서 정렬한다.

// 힙 정렬

import java.util.Arrays;

public class Main2 {
    
    // 힙 정렬
    public static void heapSort(int[] arr) {
        // 힙으로 재구성 (maxHeap 기준, 마지막 부모 노드부터)
        for(int i = arr.length / 2 - 1; i >= 0; i--) {  //arr.length/2-1은 자식 노드를 갖고 있는 부모 노드의 제일 마지막 값 인덱스
            heapify(arr, i, arr.length);
        }

        // maxHeap 기준 root 쪽을 끝 쪽으로 보내면서 재정렬 -> 오름차순
        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    //힙으로 바꾸는 메소드
    public static void heapify(int[] arr, int parentIdx, int size) {
        // 자식 노드 위치
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        // 왼쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }

        // 오른쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }

        // maxIdx 가 바뀐 경우, 부모 노드가 교체되는 것을 의미
        // 교체하고 서브 트리 검사 하도록 재귀 호출
        if(parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            heapify(arr, maxIdx, size);
        }
    }

    //두 값을 교체하는 메소드
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        heapSort(arr);
        System.out.println("힙 정렬: " + Arrays.toString(arr));
    }
}