• 힙정렬(Heap Sort) 알고리즘 :: 마이구미
    알고리즘 2018. 4. 17. 09:48

    이 글은 힙 정렬(heap sort), 힙 소트 라고 불리는 정렬 알고리즘을 다룬다.

    누구나 한번쯤은 들어봤고, 구현해본 정렬 중 하나이다.

    빠른 정렬에 분류되고, 시간복잡도가 같은 퀵정렬과 합병정렬과 함께 언급된다.

    퀵정렬 - http://mygumi.tistory.com/308

    합병정렬 - http://mygumi.tistory.com/309

    참고 링크 - https://www.geeksforgeeks.org/heap-sort/


    1. 힙 정렬이란 무엇인가?

    2. 힙 정렬은 어떻게 구현하는가?

    3. 힙 정렬은 어디에서 사용하는가?


    힙 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.

    완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다.

    힙에는 부모 노드의 값이 자식 노드의 값보다 항상 큰 최대 힙과 그 반대인 최소 힙이 존재한다. (힙 위키)

    주의할 점은 부모-자식 관계간의 이야기이고, 형제간은 고려하지 않는다.


    시간복잡도는 최악, 최선, 평균 모두 O(nlogn) 을 가진다.

    또한 불안정 정렬에 속한다. (불안정 정렬의 의미를 모른다면 참고글)


    1. 최대 힙을 구성한다.

    2. 현재 힙의 루트는 가장 큰 값이 존재하게 된다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.

    3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.


    위 과정은 사실상 힙 자체의 연산 중에서 extract 연산을 이용한다.

    extract 연산은 힙으로부터 루트를 삭제하고, 다시 힙을 구성하는 절차이다.

    그림으로 표현하면 다음과 같다. (자세한 내용은 위에서 링크한 영문으로된 위키를 참고바란다)


    힙 정렬


    위와 같이 힙에서 루트를 마지막 노드로 대체하는 모습을 보여주고 있다.

    그 후, 다시 최대 힙을 구성하는 모습은 아래와 같다.


    힙 정렬


    위와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬을 할 수 있게 된다.

    이것이 가능한 이유는 최대 힙을 구성한다는 것이 루트에 가장 큰 값이 존재한다는 의미가 되기 때문이다.

    힙을 이해한다면, 쉽게 힙 정렬을 이해할 수 있다.


    위 흐름의 전체 코드는 다음과 같다.


    public void heapSort(int[] array) { int n = array.length; // init, max heap for (int i = n / 2 - 1; i >= 0; i--) { heapify(array, n, i); // 1번 } // for extract max element from heap for (int i = n - 1; i > 0; i--) { swap(array, 0, i); // 2번 heapify(array, i, 0); // 1번 } }


    첫번째 heapify() 는 단순히 일반 배열을 힙으로 구성하는 역할을 한다.

    그 과정에서 자식 노드로부터 부모 노드를 비교한다.

    n / 2 - 1 부터 0까지는 인덱스가 도는 이유는 부모 노드의 인덱스를 기준으로 왼쪽자식노드(i * 2 + 1), 오른쪽자식노드(i * 2 + 2) 이기 때문이다. 


    두번째 heapify() 는 요소가 하나 제거된 후 다시 최대 힙을 구성하기 위함이다.

    extract 연산과 같은 처리를 하기 위해 루트를 기준으로 진행된다.


    heapify() 의 내부는 다음과 같다.


    public void heapify(int array[], int n, int i) { int p = i; int l = i * 2 + 1; int r = i * 2 + 2; // left childNode if (l < n && array[p] < array[l]) { p = l; } // right childNode if (r < n && array[p] < array[r]) { p = r; } // parentNode < childNode if (i != p) { swap(array, p, i); heapify(array, n, p); } }


    코드는 다시 최대 힙을 구성할때까지 부모 노드와 자식 노드를 스왑하면서 재귀적으로 진행된다.


    일반적으로 힙 자료구조는 힙 정렬과 함께 언급된다.

    사실상 대부분의 경우 퀵정렬 또는 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도는 높지않다.

    그렇다고 힙 자료구조 자체의 사용빈도를 말하는 것은 아니다.

    힙 자료구조는 많이 사용되고, 많은 알고리즘과 연관되어있다.


    다음은 힙 정렬에 유용한 예가 된다.


    1. 가장 크거나 작은 값을 구할 때

    2. 최대 k 만큼 떨어진 요소들을 정렬할 때


    1번의 경우는 최소 힙 또는 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 쉽게 구할 수 있다.

    2번의 경우에는 일반적으로 삽입정렬을 활용할 수 있지만, 힙 정렬을 통해서 더욱 개선할 수 있다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    private void solve() {
        int[] array = { 23010605504022020 };
     
        heapSort(array);
     
        for (int v : array) {
            System.out.println(v);
        }
    }
     
    public static void heapify(int array[], int n, int i) {
        int p = i;
        int l = i * + 1;
        int r = i * + 2;
     
        if (l < n && array[p] < array[l]) {
            p = l;
        }
     
        if (r < n && array[p] < array[r]) {
            p = r;
        }
     
        if (i != p) {
            swap(array, p, i);
            heapify(array, n, p);
        }
    }
     
    public static void heapSort(int[] array) {
        int n = array.length;
     
        // init, max heap
        for (int i = n / - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
     
        // for extract max element from heap
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }
     
    public static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    cs


    댓글 3

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:08 신고

      2영재 - 잘보았습니다. 질문이 있어 댓글 남깁니다.
      힙정렬 이라는것은 퀵정렬/합병정렬 등과 달리 배열 내에서 원소들이 정렬 되어있는 것은 아니지만 루트 노트를 pop할때마다 정렬된 결과(Max,Min에 따라 최대 혹은 최소값이)가 나오기 때문에 힙정렬이라고 하는건가요??
      => Heap 자료구조를 먼저 생각하시면 됩니다.
      말씀하신대로 Heap 자체는 항상 루트가 최대 혹은 최소입니다.
      그리고 pop 개념보다는 replace 라고 보시면 좋습니다.
      단순히 Heap 의 특성을 기반으로 하기에 힙정렬이라 부릅니다.
      힙정렬은 힙 자료구조를 기반 or 참고한 정렬 방식이라고 보시면 됩니다.

    • MintFlavor 2020.06.05 00:11

      왼쪽 자식의 인덱스가 2 * [부모 인덱스] + 1 이고
      오른쪽 자식의 인덱스가 2 * [부모 인덱스] + 2 이면
      본문의 힙 정렬에서 사용된 배열은 인덱스가 "1"이 아닌 "0"부터 시작한 건가요??

      공부 중인 책에는
      왼쪽은 2 * [부모 인덱스]
      오른쪽은 2 * [부모 인덱스] + 1
      이라고 나와서 헷갈리네요.


      if( i != p ) 는 어떠한 상황을 의미하는건가요?

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2020.06.07 15:50 신고

        트리구조에서 부모 노드와 자식 노드의 왼쪽 노드의 인덱스, 오른쪽 노드의 인덱스의 단순 계산이기에, 그림으로 그려서 확인해보시면 이해가 편하실 겁니다.

        최대 힙을 구성한다면, 더이상 힙을 구성할 필요가 없기에 재귀를 멈추는 조건입니다.

Designed by Tistory.