[정렬] 힙 정렬 :: 늦깎이 IT

---

힙 정렬 내용은 2019/04/16 - [늦깎이 IT] - [정렬] 힙 정렬 (수정) :: 늦깎이 IT 에서 다시 수정하여 포스팅하였습니다.

---

지난 번 힙 기반의 우선순위 큐를 구현한데 이어, 오늘은 힙 정렬을 구현하겠습니다.

힙에 대한 설명은 아래 포스팅을 참고하시기 바랍니다.

2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙

[관련 알고리즘 문제]

2019/02/17 - [알고리즘 문제/알고스팟] - [알고스팟 RUNNINGMEDIAN] 변화하는 중간값

우선 힙은 1차원 배열로 표현할 수 있습니다. 우리가 보기에는 '완전 이진 트리'인 힙의 구조가 어떻게 배열로

표현할 수 있는지 생각해봅시다. 

다음과 같이 무작위 데이터가 저장된 배열과 완전 이진트리가 있다고 가정해봅시다.

위의 배열과 트리의 연관성을 아시겠나요? 모르시겠다면 바로 다음 그림을 보시죠.

배열의 인덱스를 표시하고 트리에 저장된 데이터에도 각각 인덱스를 부여해주니 배열과 트리가 같은 순서대로

데이터를 저장하고 있다는 것을 확인할 수 있습니다.

사실 완전 이진 트리는 우리가 '트리'라는 자료구조를 강조하면서 트리형태로 그림(?)을 그릴 뿐이지

1차원 배열로 똑같이 표현할 수 있습니다.

그렇다면, 배열에서 어떻게 자식 노드에 접근할 수 있을까요?

현재 0번째 인덱스의 왼쪽, 오른쪽 자식노드는 인덱스 1과 2입니다. 이를 수식으로 표현하면

1) 왼쪽 자식 노드 = 부모 노드 X 2 + 1

2) 오른쪽 자식 노드 = 부모 노드 X 2 +2

3) 부모 노드 = (자식 노드 - 1) / 2

이제 완전 이진 트리를 배열로 표현(?) 및 접근하는 방법을 알았으니 입력으로 주어지는 배열을 

힙으로 변환하는 방법에 대해 알아보겠습니다. (이 포스팅에서는 최대힙을 기준으로 설명합니다.)

우선 각각의 노드들을 탐색하며 자리를 바꿔주는 과정을 거치게 됩니다.

1) 루트 노드는 자신의 자식 노드들과 값을 비교한다.

2) 자식 노드들 중 큰 값과 자기 자신(부모 노드)를 비교하여 자식 노드의 값이 더 크다면 자리를 바꾼다.

3) 자리를 바꾸지 않았다면 종료한다.

4) 자리를 바꿨다면, 자리를 바꾼 자리에서 다시 1~3번 과정을 반복한다.

위와 같은 과정을 그림으로 표현하면 다음과 같습니다.

(자식 노드와 비교를 진행해야 하기 때문에, 자식 노드가 존재하지 않는 단말 노드(9 ,7 ,5 ,8)들은 위와 같은 과정을

거치지 않습니다.)

이와 같은 과정을 거치고 나면 배열을 힙으로 변환시킬 수 있습니다.

[힙 변환 과정 Code - 1]

public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
}
 
public static void heapify(int[] arr, int root, int length) {
 
        int parent = root;
        int leftChild = parent * 2 + 1;
        int rightChild = parent * 2 + 2;
 
        if (leftChild < length && arr[parent] < arr[leftChild])
            parent = leftChild;
 
        if (rightChild < length && arr[parent] < arr[rightChild])
            parent = rightChild;
 
        if (root != parent) {
            int temp = arr[root];
            arr[root] = arr[parent];
            arr[parent] = temp;
            heapify(arr, parent, length);
        }
}

[힙 변환 과정 Code - 2]

public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--)
            heapify(arr, i, arr.length);
    }
 
    public static void heapify(int[] arr, int root, int length) {
 
        int child = root * 2 + 1;
        while (child < length) {
 
            if (child + 1 < length && arr[child] < arr[child + 1])
                child += 1;
 
            if (arr[root] < arr[child]) {
                int temp = arr[root];
                arr[root] = arr[child];
                arr[child] = temp;
            }
            root = child;
            child = root * 2 + 1;
        }
 
    }

[힙 변환 과정 Code - 3]

public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }
 
    public static void heapify(int[] arr, int root, int length) {
 
        int child = root * 2 + 1;
        if (child + 1 < length && arr[child] < arr[child + 1])
            child += 1;
 
        if (child < length && arr[root] < arr[child]) {
            int temp = arr[root];
            arr[root] = arr[child];
            arr[child] = temp;
        }
        if (child < length / 2)
            heapify(arr, child, length);
    }

[힙 정렬하기]

이제 주어진 배열을 힙으로 변환했다면 정렬할 차례입니다. 정렬하는 과정은 다음과 같습니다.

1) 루트 노드와 마지막 노드의 위치를 바꿉니다.

2) 힙의 크기가 1줄어든 것으로 간주합니다. 즉, 마지막 값은 힙의 일부가 아니라고 가정합니다.

3) 루트노드에 대해서 Heapify를 진행한다.

4) 1~3번을 반복한다.

위 과정을 그림으로 표현해봤습니다.

위와 같은 정렬 과정을 거치면 정렬이 완료됩니다.

[힙정렬 전체 Code - 1]

 
public class Practice {
 
    public static void main(String[] args) {
        int[] arr = new int[] { 6, 2, 4, 9, 7, 5, 8 };
        heapSort(arr);
        showHeap(arr);
        
    }
 
    public static void heapSort(int[] arr) {
        buildMaxHeap(arr);
 
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i - 1];
            arr[i - 1] = temp;
            heapify(arr, 0, i - 1);
        }
    }
 
    public static void heapify(int[] arr, int root, int length) {
 
        int parent = root;
        int leftChild = parent * 2 + 1;
        int rightChild = parent * 2 + 2;
 
        if (leftChild < length && arr[parent] < arr[leftChild])
            parent = leftChild;
 
        if (rightChild < length && arr[parent] < arr[rightChild])
            parent = rightChild;
 
        if (root != parent) {
            int temp = arr[root];
            arr[root] = arr[parent];
            arr[parent] = temp;
            heapify(arr, parent, length);
        }
    }
 
    public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }
 
    public static void showHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
}