힙 정렬

힙 정렬은 선택 정렬을 응용한 알고리즘이다. 힙을 사용하여 정렬한다.

여기서 '힙'은 '부못값이 자식값보다 항상 크다'라는 조건을 만족하는 완전이진트리이다.

모든 부모와 자식의 관계는 항상 부모값>= 자식값

 

힙정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다.

- 힙에서 가장 큰 값인 루트를 꺼냅니다

- 루트 이외의 부분을 힙으로 만듭니다

이 작업을 반복한다.

import java.util.Arrays;

public class HeapSort {

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

    public static void main(String[] args) {
        System.out.println("힙정렬");
        System.out.println("요솟수: 7 ");
        int nx = 7;
        int[] x = new int[]{6,4,3,7,1,9,8};

        heapSort(x, nx);

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

    }

    static void heapSort(int[] a, int n) {
        for(int i = (n-1) / 2; i >=0; i--) // a[i]~a[n-1]를 힙으로 만듦
            downHeap(a, i, n-1);
        
        for(int i = n-1; i>0; i--){
            swap(a,0,i); // 가장 큰 요소와 아직 정렬되지 않은 마지막 요소를 교환
            downHeap(a,0,i-1);
        }
    }

    // a[left]~a[right]를 힙으로 만듦
    /*
    * 힙요소를 배열에 저장하면 생기는 관계
    * 부모는 a[(i-1)/2]
    * 왼쪽 자식은 a[i*2+1]
    * 오른쪽 자식은 a[i*2+2]
    * */
    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;
    }
}

 

힙 정렬의 시간복잡도는 O(n log n)