[Algorithm] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

 

■ 정의

- 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조
- 힙(heap)을 사용하여 정렬하는 알고리즘

 

· 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리

· 최대힙: 부모노드 값(key 값)  ≤  자식노드 값 (key 값)
· 최소힙: 부모노드 값(key 값)  ≥  자식노드 값 (key 값)

■ 인덱스 관계

- 부모노드 인덱스:  a[(i-1) / 2]
- 왼쪽 자식노드 인덱스:  a[i * 2 + 1]
- 오른쪽 자식노드 인덱스: a[i * 2 + 2]

 

■ 힙 정렬 과정

Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거

Step 2. 다시 힙을 재구조화 시키고 9를 제외한 최대 힙이 root로 이동

Step 3. 새로 생긴 최대 힙을 배열에 9를 제외한 마지막 배열과 교환 (8이 root 로 이동)

Step 4. 위 과정을 정렬이 될 때까지 반복

 

■ Code

import java.util.Scanner;

public class HeapSort {
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void downHeap(int[] a, int left, int right){
        int temp = a[left];
        int child;
        int parent;

        for(parent = left; parent < (right + 1) / 2; parent = child){
            int cl = parent * 2 + 1;
            int cr = cl + 1;
            child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
            if(temp >= a[child])
                break;
            a[parent] = a[child];
        }
        a[parent] = temp;
    }

    static void heapSort(int[] a, int n){
        for(int i = (n - 1) / 2; i >= 0; i--)
            downHeap(a, i, n - 1);
        for(int i = n - 1; i > 0; i--) {
            swap(a, 0, i);
            downHeap(a, 0, i - 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("힙 정렬");
        System.out.print("요솟수: ");
        int nx = sc.nextInt();
        int[] x = new int[nx];

        for(int i = 0; i < nx; i++){
            System.out.print("x[" + i + "]: ");
            x[i] = sc.nextInt();
        }

        heapSort(x, nx);

        System.out.println("오름차순으로 정렬했습니다.");
        for(int i = 0; i < nx; i++)
            System.out.println("x[" + i + "] = " + x[i]);
    }
}