[알고리즘] 힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

• 병합 정렬, 퀵 정렬만큼 빠른 정렬 알고리즘

• 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리

• 힙의 가장 중요한 원칙

  • 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소의 크기보다 크다.
  • 트리에서 가장 큰 원소는 항상 트리의 루트에 존재한다.

• 힙의 모양 규칙

  • 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
  • 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

• 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방식

  • 크기가 n인 완전 이진트리
  • 힙(Heap) 이란 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진트리를 기반으로 하는 자료구조
  • 최댓값이란 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
  • 최솟값이란 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
  • 키 값의 대소 관계는 오직 부모 노드와 자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다.

• 힙을 사용할 경우 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(logN) 시간에 수행할 수 있다.

코드 설계

• 힙 구조의 규칙
  • A[i]에 대응되는 노드의 왼쪽 자손은 A[2 * i + 1]에 대응된다.
  • A[i]에 대응되는 노드의 오른쪽 자손은 A[2 * i + 2]에 대응된다.
  • A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응된다.(나눗셈 결과는 내림한다.)
• 정렬 과정
  • 마지막 노드의 부모 노드부터 시작하여 root 노드순으로 검색한다.
  • 정렬의 과정은 최댓값을 검증하여 정상적인 힙 구조인지 확인, 아닐 경우 child와 parent를 변경

코드 구현

    private void swap(int[] A, int pre, int post) {
        System.out.println("swap: \tA[" + pre + "]=" + A[pre] + " <> A[" + post + "]=" + A[post]);
        int tmp = A[pre];
        A[pre] = A[post];
        A[post] = tmp;
    }
    /**
     * 힙 정렬
     * @param A
     */
    private void heapSort(int[] A) {
        int aLength = A.length - 1; // 배열의 실 길이
        int parentIdx = aLength / 2;

        // 마지막 노드의 부모 노드부터 시작하여 root 노드 방향으로 거슬러 올라감
        for (int i = parentIdx; i >= 0; i--) maxHeapify(A, A.length, i);

        for(int i = aLength ; i > 0 ; i--) { // 원소가 하나 남을 때까지 반복
            swap(A, 0, i); // 배열의 마지막 요소 값을 루트로 변경
            maxHeapify(A, i, 0);
        }
    }

    /**
     * 배열 A를 힙으로 만드는 메서드
     * 루트에 있는 가장 큰 값을 빼내어 마지막 요소와 바꾸고,
     * 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복하여 정렬을 수행

     * @param A
     * @param length
     * @param i 
     */
    private void maxHeapify(int[] A, int length, int i) {
        int parent = i; // parent index
        int leftChild = (i * 2) + 1; // leftChild index
        int rightChild = (i * 2) + 2; // rightChild index


        // leftChild가 parent보다 클 경우
        if(leftChild < length && A[parent] < A[leftChild]) {
            parent = leftChild;
        }

        // rightChild가 parent보다 클 경우
        if(rightChild < length && A[parent] < A[rightChild]) {
            parent = rightChild;
        }

        if(i != parent) {
            swap(A, parent, i);
            maxHeapify(A, length, parent-1);
        }
    }

• 과정

             01
            ／＼
     04              05
    ／＼            ／＼
 07      02      06      03
／            
08

A[7]=8 < swap > A[3]=7
             01
            ／＼
     04              05
    ／＼            ／＼
 08      02      06      03
／            
07

A[5]=6 < swap > A[2]=5
             01
            ／＼
     04              06
    ／＼            ／＼
 08      02      05      03
／            
07

A[3]=8 < swap > A[1]=4
             01
            ／＼
     08              06
    ／＼            ／＼
 04      02      05      03
／            
07

A[1]=8 < swap > A[0]=1
             08
            ／＼
     01              06
    ／＼            ／＼
 04      02      05      03
／            
07

A[0]=8 < swap > A[7]=7
             07
            ／＼
     01              06
    ／＼            ／＼
 04      02      05      03
／            
08

A[0]=7 < swap > A[6]=3
             03
            ／＼
     01              06
    ／＼            ／＼
 04      02      05      07
／            
08

A[2]=6 < swap > A[0]=3
             06
            ／＼
     01              03
    ／＼            ／＼
 04      02      05      07
／            
08

A[3]=4 < swap > A[1]=1
             06
            ／＼
     04              03
    ／＼            ／＼
 01      02      05      07
／            
08

A[5]=5 < swap > A[2]=3
             06
            ／＼
     04              05
    ／＼            ／＼
 01      02      03      07
／            
08

A[0]=6 < swap > A[5]=3
             03
            ／＼
     04              05
    ／＼            ／＼
 01      02      06      07
／            
08

A[2]=5 < swap > A[0]=3
             05
            ／＼
     04              03
    ／＼            ／＼
 01      02      06      07
／            
08

A[0]=5 < swap > A[4]=2
             02
            ／＼
     04              03
    ／＼            ／＼
 01      05      06      07
／            
08

A[1]=4 < swap > A[0]=2
             04
            ／＼
     02              03
    ／＼            ／＼
 01      05      06      07
／            
08

A[0]=4 < swap > A[3]=1
             01
            ／＼
     02              03
    ／＼            ／＼
 04      05      06      07
／            
08

A[2]=3 < swap > A[0]=1
             03
            ／＼
     02              01
    ／＼            ／＼
 04      05      06      07
／            
08

A[0]=3 < swap > A[2]=1
             01
            ／＼
     02              03
    ／＼            ／＼
 04      05      06      07
／            
08

A[1]=2 < swap > A[0]=1
             02
            ／＼
     01              03
    ／＼            ／＼
 04      05      06      07
／            
08

A[0]=2 < swap > A[1]=1
             01
            ／＼
     02              03
    ／＼            ／＼
 04      05      06      07
／            
08

분석

• 힙 정렬은 선택 정렬을 응용한 알고리즘
• 첫 요소를 꺼내는 것만으로 가장 큰 값이 구해지므로 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들어야 그 다음에 꺼낼 요소도 가장 큰 값을 유지한다.
• 따라서 단순 선택 정렬에서 가장 큰 요소를 선택할 때의 시간 복잡도 O(n)의 값을 한 번에 선택할 수 있어 O(1)로 줄일 수 있다.
• 복잡도 분석
  • 힙으로 만드는 작업의 시간 복잡도 O(logn)
  • 힙으로 만드는 작업을 요소의 개수 만큼 반복하므로 O(n logn)