힙 정렬 (Heap Sort)

힙 (Heap)

- 완전 이진 트리 종류 중 한가지

- 우선순위 큐에 사용이 됨

- Max Heap, Min Heap 두가지 종류가 있음

- 완전한 정렬 형태가 아닌 느슨한 정렬 형태 (부모 노드가 두 자식 노드보다 큼)

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

 

힙 정렬 (Heap Sort)

- 위에서 제시한 Heap 구조를 통해서 정렬을 하는 알고리즘

- 구현이 내림차순일지 오름차순일지에 따라 또, Top-down 인지 Bottom-up 인지에 따라 달라짐

- 여기서는 Top-down 방식의 오름차순을 구현함

 

정렬 알고리즘

 

알고리즘을 설명하기 전 주요 알고리즘인 heapify에 대한 설명

- heap 노드를 구성하는 알고리즘

- 부모 노드와 자식 노드 간에 값을 비교해서 큰 값을 찾아 교체

- 만약 교체 했다면 교체된 자식 노드를 부모로 생각하고 다시 비교를 실행

- 자식 노드가 존재하지 않거나, 자식 노드 중에 비교할 대상이 없다면 종료

- 완료하고나면 느슨한 정렬이 완성됨.

 

1. heapify를 통해 Max Heap 형태의 이진 트리를 구성 (단, 이때 비교 시작 인덱스는 자식을 가진 마지막 부모 노드)

2. 최대 값인 0번째 노드와 맨 마지막 노드의 값을 교체 (최대 값을 맨 마지막 자리에 고정)

3. 교체된 0번째 노드의 값을 heapify 함 (이때 heapify 비교 최대 인덱스는 교체한 맨 마지막 노드 전까지)

4. 교체하는 0번째 노드의 인덱스를 한칸씩 땡기면서 반복

 

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class HeapSort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void buildHeap(int[] arr) {
        // MAX 빌드
        // arr.length/2 - 1 ==> 자식을 가진 노드 중 마지막 노드 (마지막 부모 노드)
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyMax(arr, arr.length, i);
//            heapifyMin(arr, arr.length, i);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, i, 0);
            heapifyMax(arr, i, 0);
//            heapifyMin(arr, arr.length, i);
        }
    }

    public static void heapifyMax(int arr[], int length, int parentIdx) {
        int childIdx = parentIdx * 2 + 1;
        while (childIdx < length) {
            if (childIdx + 1 < length && arr[childIdx] < arr[childIdx + 1]) {
                childIdx++;
            }

            if (arr[parentIdx] < arr[childIdx]) {
                swap(arr, parentIdx, childIdx);
                parentIdx = childIdx;
                childIdx = parentIdx * 2 + 1;
            } else {
                break;
            }
        }
    }

    public static void heapifyMin(int arr[], int length, int parentIdx) {
        int childIdx = parentIdx * 2 + 1;
        while (childIdx < length) {
            if (childIdx + 1 < length && arr[childIdx] > arr[childIdx + 1]) {
                childIdx++;
            }

            if (arr[parentIdx] > arr[childIdx]) {
                swap(arr, parentIdx, childIdx);
                parentIdx = childIdx;
                childIdx = parentIdx * 2 + 1;
            } else {
                break;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int _loop = Integer.parseInt(br.readLine());

        int arr[] = new int[_loop];
        for (int i = 0; i < _loop; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();
        System.out.println();

        buildHeap(arr);

        System.out.println("FINISH");
        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
    }
}