힙 정렬 (Heap Sort)

HaYeong Jang·2021년 9월 6일

Heap Sort 알고리즘 힙 정렬

[CS] 자료구조 & 알고리즘

목록 보기

4/5

힙 정렬(Heap Sort)이란?

힙(Heap) 자료구조를 기반으로한 정렬 방식
내림차순 정렬을 하고 싶을 땐 최대 힙을, 오름차순 정렬을 하고 싶을 땐 최소 힙을 구성하면 된다.

과정 (최소 힙)

삽입

삭제

코드

public static void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

public static void heapify(int[] arr, int parent, int size) {
    int temp_parent = parent;
    int left_child = parent * 2 + 1;
    int right_child = parent * 2 + 2;

    if (left_child < size && arr[temp_parent] > arr[left_child])
        temp_parent = left_child;

    if (right_child < size && arr[temp_parent] > arr[right_child])
        temp_parent = right_child;

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

public static void main(String[] args) {
    int[] arr = new int[]{7, 3, 22, 6, 2, 14, 1};
    int len = arr.length;

    // heapify를 통해 초기 배열을 min heap으로 만듦
    for (int i = len / 2 - 1; i >= 0; --i)
        heapify(arr, i, len);

    // 루트노드를 뒤로 넘기고(삭제) 나머지 원소들을 heap으로 만듦
    for (int i = len - 1; i > 0; --i) {
        swap(arr, 0, i);    
        heapify(arr, 0, i); 
    }
}