힙

힙 정렬을 익히기 전에 필요한 힙에 관한 개념

부모 노드 값이 자식 노드 값 보다 항상 큰 조건을 만족(부모 >= 자식) 하는 완전 이진 트리
형제 관계의 노드는 대소 관계를 비교하지 않는다.

이진 트리 구조를 배열에 저장하여 힙 만들기

위와 같은 힙의 성질을 띄는 이진트리를 배열로 저장한 형태는 다음과 같다.

배열에 힙의 요소를 저장할 때 찾을 수 있는 규칙성

• 특정 노드의 부모 노드 인덱스: a[(i-1)/2]

• 왼쪽 자식의 인덱스: a[i * 2 + 1]

• 오른쪽 자식의 인덱스: a[i * 2 + 2]

---

힙 정렬

가장 큰 값이 루트에 위치하는 특징을 이용한 정렬 알고리즘

1. 루트 노드를 꺼낸다.
2. 비어있는 루트 노드에 힙의 마지막 노드를 옮긴다.
3. 이진트리를 다시 힙으로 구성한다.

---

루트 노드 10을 꺼냈다. 어떤 노드가 와야할까?

트리의 마지막 노드를 루트 노드로 옮긴다.

위의 트리는 힙의 성질을 띄고 있는가? NO

힙의 성질을 띄도록 노드를 옮긴다.

배열을 힙으로 만드는 방법

위 그림 처럼 아래 부분의 작은 부분 트리부터 시작해 올라가는 Bottom-up 방식을 사용하여 배열을 힙으로 만들 수 있다.

선택 정렬이 선형 탐색으로 최소값을 찾아 맨왼쪽의 값과 차례로 자리를 변경시키는 것과 같이 힙 정렬도 최대 값을 가진 루트 노드를 마지막 요소와 교체하고 다시 힙구조로 만들어 최대 루트 노드를 그 다음 마지막 요소와 변경하면서 정렬을 진행한다.

코드

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

        /*
        * 자식노드는 다시 부모노드가 된다 (parent = child)
        * */
        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; // cr이 right 보다 크지 않는 조건이 필요.

            // 부모 노드가 자식노드보다 크면 현재 힙 상태의 배열임을 뜻하므로 종료
            if (temp >= a[child]) {
                break;
            }

            // 부모 노드가 자식 노드보다 작다면 부모 노드 값을 더 큰 자식 노드 값으로 교체한다.
            a[parent] = a[child];
        }

        a[parent] = temp;
    }

    private static void heapSort(int[] a, int n) {
        System.out.println("==== 입력으로 들어온 배열 힙으로 만들기 ==== ");
        System.out.println(Arrays.toString(a));
        /*
        * n 이 7이라면 i = 3
        * 그러면 3, 6 사이를 힙 처리
        * */
        for(int i = (n - 1) / 2; i >= 0; i--) {
            downHeap(a, i, n - 1);
        }

        System.out.println(Arrays.toString(a));
        System.out.println("==== 배열을 힙 상태로 변경 완료 ====");

        for (int i = n - 1; i > 0; i--) {
            swap(a, 0, i);
            downHeap(a, 0, i - 1);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }