힙 정렬(heap sort)

• 합병 정렬의 문제점
  • 정렬한 레코드 수에 비례하여 저장 공간이 추가로 필요
• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성

입력 리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19)

• 최대 히프 구조를 만든다

• 히프의 첫번째 레코드와 마지막 레코드 교환

  • 최대 키를 가진 레코드가 정렬된 배열의 정확한 위치에 자리잡게 됨

• 히프의 크기를 줄인 후 히프를 재조정

힙 정렬 분석

• 일정한 양의 저장 공간만 추가로 필요
• 최악의 경우 연산 시간과 평균 연산 시간 : O(nlogn)
  • 합병 정렬보다 약간 느림

구현

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        // 정렬 되지 않은 배열
        int[] arr = {26, 5, 77, 1, 61, 11, 59, 15, 48, 19};

        /*
         * < maxHeap 만들기 >
         * - 부모노드의 값이 자식노드의 값들보다 큰 형태
         * - i의 초기값은 배열의 제일 끝 자식노드의 부모노드부터 시작한다.
         */
        for(int i=arr.length/2-1;i>=0;i--){
            heapify(arr, arr.length, i);
        }

        // 정렬하기
        for(int i=arr.length-1;i>=0;i--){
            swap(arr, i, 0); // 최상단 노드와 최하단 노드 값을 교환한다.
            heapify(arr, i-1, 0); // 루트노드를 기준으로 최대힙을 만든다.
        }

        // 출력
        System.out.println(Arrays.toString(arr));
    }

    public static void heapify(int[] arr, int size, int pNode){

        int parent = pNode; // 부모노드
        int lNode = pNode * 2 + 1; // 왼쪽 자식노드
        int rNode = pNode * 2 + 2; // 오른쪽 자식노드

        // size > lNode => 인덱스 범위를 넘어서는지 확인하기 위함
        if(size > lNode && arr[parent] < arr[lNode]){
            parent = lNode;
        }

        if(size > rNode && arr[parent] < arr[rNode]){
            parent = rNode;
        }

        // parent에 저장된 값은 자식노드 중 큰 값이 있다면 큰 값의 인덱스 값이 남아있을 것이다.
        // 초기에 설정한 부모노드의 인덱스와 다르다면 교환을 해준다.
        if(parent != pNode){
            swap(arr, pNode, parent);

            /*
             * 노드와 자리를 바꾸면 최대힙 기준에 맞지 않을 수 있기 때문에
             * 바뀐 자식노드 아래 최대힙으로 맞춰주기 위함
             */
            heapify(arr, size, parent);
        }
    }

    public static void swap(int[] arr, int i, int j){

        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
}

---

참조

• 고려대학교 김상곤 교수님 강의 중
• [JAVA] 힙정렬(Heap Sort) 알고리즘