[알고리즘] 정렬 - 힙 정렬

1. 힙 정렬

• 힙 트리구조를 이용하는 정렬방법으로 병합, 퀵 정렬만큼 빠른 알고리즘
• 힙 정렬을 이해하기 위해서는 이진 트리, 완전 이진 트리, 힙에 대해서 알고 있어야 한다.

1) 이진 트리(Binary Tree)

• 모든 노드의 자식 노드가 2개 이하인 노드
• 데이터를 표현할 때 각 노드에 담은 뒤 노드를 두 개씩 이어 붙이는 구조

이미지 출처 :  https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

2) 완전 이진 트리

• 데이터가 루트 노드부터 시작, 자식 노드가 왼쪽, 오른쪽 자식 노드로 차근차근 들어가는 구조

이미지 출처 :  https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

 

3) 힙

• 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리
• 최대 힙 : 부모 노드가 자식 노드보다 큰 힙
• 최소 힙 : 부모 노드가 자식 노드보다 작은 힙

• → 아래와 같이 트리 안에서 특정 노드 때문에 최대 힙이 붕괴되는 경우가 있음 ⬇️

→ 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용해야 함

힙 생성 알고리즘 : 자식 노드 중 부모 노드(5)보다 큰 값(7)이 있을 경우 부모와 자식을 바꿔줌(5 ↔ 7)

• 시간 복잡도 : 한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가 → O(logN)
• → 데이터 개수가 1024개일 경우 10번 정도만 내려가면 됨

전체 트리구조에 힙 생성 알고리즘을 수행하면 → 힙 구조가 됨

→ 힙 구조를 만드는 필요한 시간 복잡도 : N * logN

 

2.  힙 정렬 알고리즘의 순서

1. 데이터를 완전 이진트리에 삽입되는 순서대로 인덱스를 붙여서 배열에 담는다
2. 배열의 모든 원소를 기분으로 힙 생성 알고리즘을 적용하여 트리 전체를 힙 구조로 만든다 O(N * logN)
3. 만들어진 최대 힙(최소 힙)을 가지고 정렬을 시작
4. 루트 값을 가장 뒤 쪽으로 보내고 힙 트리의 크기를 1씩 감소
5. 가장 뒤로 이동한 루트를 제외하고 나머지를 대상으로 힙 생성 알고리즘을 수행
6. 다시 루트와 가장 뒤에 있는 원소와 바꿈
7. 반복

 

3. 코드로 알아보기

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {

        int[] arr = new int[]{7, 6, 5, 8, 3, 5, 9, 1, 6};

        System.out.println("전 : " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("후 : " + Arrays.toString(arr));

    }

    private static void heapSort(int[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0); // 요소를 제거 후 다시 최대 힙
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        /**
         * 부모 노드(인덱스) 찾기 : (자식 노드(인덱스) - 1) / 2
         * 왼쪽 자식 노드 찾기 : 부모 노드 * 2 + 1
         * 오른쪽 자식 노드 찾기 : 부모 노드 * 2 + 2
         */

        // i : 부모 노드의 인덱스
        int p = i;
        int lNode = i * 2 + 1; // 왼쪽 자식 노드
        int rNode = i * 2 + 2; // 오른쪽 자식 노드

        // 왼쪽 자식 노드와 비교
        // 자식인덱스가 트리의 크기를 넘지 않고 부모 노드보다 값이 클 경우 가장 큰 값을 가지는 인덱스를 lnode의 값으로 바꿔준다
        if (lNode < n && arr[p] < arr[lNode]) {
            p = lNode;
        }
        // 오른쪽 자식 노드와 비교
        if (rNode < n && arr[p] < arr[rNode]) {
            p = rNode;
        }

        // i != p : 위의 if문에서 p값이 바꼈다는 뜻 -> 자식노드가 부모노드보다 크다
        // -> 부모 노드랑 자식 노드 자리를 바꾸고 다시 힙 생성 알고리즘
        if (i != p) {
            swap(arr, p, i);
            heapify(arr, n, p);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}