힙 정렬

정순동·2024년 2월 21일
알고리즘정렬힙 정렬

알고리즘

목록 보기
22/33

힙 정렬이란?

힙 정렬이란? 힙(heap)을 사용하여 정렬하는 알고리즘이다. 힙은 '부못값이 자식 값보다 항상 크거나 항상 작게'라는 조건을 만족하는 완전이진트리를 말한다.

트리란??
트리는 자료형태가 나무처럼 생겼다고 해서 트리입니다.
트리의 가장 윗부분을 루트(root)라고 하며, 요소간의 상하 관계가 있다.
여기서 위에있는 요소가'부모'이고 아래에 있는 요소들이'자식'이다. 그리고 자식 간의 관계를 '형제(sibling)'라고 한다.
또한, 맨 아래 요소들을 잎(leaf)라고 한다. leaf는 루트와 다르게 여러개일 수 있다.
완전이진트리?
아래에서 볼 트리는 완전이진트리로, 트리의 한 종류이다.
완전이진트리의 특징은 '완전이진'상태라는 것이다. 여기서 '완전'이라는 말은 '부모는 자식을 왼쪽부터 추가하는 모양을 유지한다'는 뜻이고, '이진'이라는 말은 '부모가 가질 수 있는 자식의 개수는 최대 2개'라는 뜻이다.

※ 본래 힙은 '쌓아 놓음'또는 '쌓아 놓은 더미'를 뜻한다. 만약 힙 정렬이 어렵거나 트리를 잘 모르겠다면 관련 글을 읽고 오자.


위 그림은 힙이 아닌 완전이진트리이다. 이런 완전이진트리를 위에서 말한 '부모의값이 자식의값보다 항상 크거나 항상 작게'만들면 힙이 된다.

아래의그림이 위의 완전이진트리를 힙으로 바꾼 예시이다.

이렇게 힙은 항상 '부못값 >= 자식값' 혹은 항상 '부못값 <= 자식값' 으로 만들면 된다.
위 그림의 경우 전자의 힙인 'Max Heap'형태의 힙으로 부르고 만약 4가 루트값으로 오고 그 아래 부못값 <= 자식값으로 힙을 만드는 경우는 후자인 'Min Heap'으로 불린다.

힙에서 부모와 자식 사이의 대소 관계는 일정하나, 형제(sibling)사이의 대소 관계는 일정하지 않다. 바로위 Max Heap그림에서도 7,8은 왼쪽→오른쪽으로 잘 정렬돼 있지만 6,5의 경우 반대로 저장돼 있는것이 확인 가능하다.

힙 정렬의 시간 복잡도

힙 정렬은 선택 정렬을 응용한 알고리즘이다.

단순 선택 정렬에서는 아직 정렬되지 않은 부분의 모든 요소를 대상으로 가장 큰 값을 선택 힙 정렬은 첫 요소가 무조건 가장 큰 값을 꺼낼 수 있다.

하지만 힙 정렬에서는 아래에서 루트를 정렬한 트리를 '다시 힙으로 만들기'라는 과정이 필요하다.(아래에서 설명함)

이에따라 각각 시간 복잡도를 구하자면 가장 큰 요소를 선택하는 복잡도는 O(n)이고, 다시 힙으로 만들기 작업을 수행하는 복잡도는 O(log n)이다.

결국 '다시 힙으로 만들기'를 반복하므로, 정렬 전체에 필요한 시간 복잡도는 단순 선택 정렬이 O(n^2), 힙 정렬은 O(n log n)으로 힙 정렬이 더 빠르다.

힙을 배열로 표현하기

자 이제, 아래 그림의 힙의 요소들을 배열에 저장하는 과정을 살펴보자 먼저 가장 위쪽에 있는 루트값 10을 heapArr[0]에 넣는다. 그리고 한 단계 아래 내려가 각 요소를 왼쪽→오른쪽으로 따라가며 배열에 넣는다.

그림판으로 그림 그리기 너무 어렵고
int[] heapArr = {10,9,5,8,3,2,4,6,7,1};

이 과정을 거쳐 힙의 요소를 배열에 저장한다면, 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립한다.

  • 부모는 a[(i-1) / 2]
  • 왼쪽 자식은 a[i x 2 + 1]
  • 오른쪽 자식은 a[i x 2 + 2]

a[3]의 요소8을 기준으로 하여 위의 관계가 성립하는지 한번 살펴보자.

  • a[3]의 부모는 a[(3-1) / 2]로 a[1]인 9이다.
  • a[3]의 왼쪽 자식은 a[3 x 2 + 1]로 a[7]인 6이다.
  • a[3]의 오른쪽 자식은 a[3 x 2 + 2]로 a[8]인 7이다.

모두 위의 관계를 만족한다.

힙 정렬 알아보기

이 포스트에서는 'Max Heap'으로 오름차순 정렬을 한다. 'Min Heap'을 사용하면 내림차순 정렬도 가능하겠다.
힙 정렬은 '가장 큰 값이 루트에 위치'한다는 특징을 이용한 정렬 알고리즘이다. 구체적으로 살펴보면 아래와 같은 작업을 반복한다.

  1. 힙에서 가장 큰 값인 루트를 꺼낸다.
  2. 루트 이외의 부분을 힙으로 만든후, 1로 넘어간다.

위의 과정에서 꺼낸 값을 늘어놓으면 배열은 정렬을 마치게된다.

즉, 힙 정렬은 선택 정렬을 응용한 알고리즘으로, 힙에서 가장 큰 값인 루트를 꺼낸 뒤 남은 요소에서 다시 가장 큰 값을 구해야한다.

힙으로 구성된 10개의 요소에서 가장 큰 값을 없애면 나머지 9개의 요소들 중에서 가장 큰 값을 루트로 정해야 한다.

따라서 나머지 9개의 요소로 구성된 트리도 힙이 되도록 재구성해야 한다.

루트를 없애고 힙 상태 유지하기

그렇다면 루트를 없애고 힙 상태를 어떻게 유지할까?

다음의 a,b,c,d과정을 살펴보며 알아보자.

A

과정 A. 힙에서 루트인 10을 꺼낸다. 그런 다음 비어 있는 루트 위치로 힙의 마지막 요소인 1을 넣는다.
오른쪽 그림처럼 된 힙은, 방금 옮긴 1을 제외하고는 힙 상태를 유지하고 있다. 따라서 방금 옮긴 1만 알맞은 위치로 옮기면 전체 트리가 힙 상태를 유지한다.

B

과정 B. 이제 루트로 옮긴 1을 알맞은 위치로 보내기 위해 자식요소를 살펴보자.
1의 자식은 9,5이다. 우리가 만든 힙은 'Max Heap'으로 힙이 되려면 이 3개의 값 가운데 가장 큰 값이 위쪽에 있어야한다. 따라서 9,5,1중 가장 큰 9가 맨 위(루트)가 된다.

C

과정 C. 1을 계속 옮겨보자. 1의 자식은 이제 8과 3이다. 앞에서와 마찬가지로 1,3,8 중 8이 가장 크기에 1과 8을 옮긴다.

D

과정 D. 1을 계속 옮겨보자. 1의 자식은 6과 7이고 1,6,7중 7과 교환한다.

이렇게 만든 트리는 힙 상태를 유지하게 된다. 여기에서는 1을 가장 아래까지 옮겼다. 하지만 항상 요소를 맨 아래까지 옮겨야 하는것은 아니며, 옮길 요소에 따라 다르다.(이경우 1이라 웬만하면 맨 아래까지 가게됨)
옮길 요소가 자식 요소2개보다 더 크면 바꿀 수 없다.

루트를 없앤 다음 다시 힙을 만들기 위해 알맞은 위치로 내려보는 절차를 정리하면 아래와 같다.

  1. 루트를 꺼낸다.
  2. 마지막 요소를 루트로 옮긴다.
  3. 자기보다 큰 값을 갖는 자식 요소와 자리를 바꿔가며 아래쪽으로 내린다. 이때 자식값이 더 작거나 잎(leaf, 끝)에 다다르면 작업을 종료한다.

힙 정렬 알고리즘 살펴보기

과정 A,B,C를 보면서 힙 정렬 알고리즘의 흐름을 살펴보자.

	{10,9,5,8,3,2,4,6,7,1}

위 힙 배열을 사용할 것이고, a[9]부터 정렬된 요소가 들어와 a[0]까지 정렬된 요소가 들어오면 위 배열의 힙 정렬이 끝나게 된다.

A

힙의 루트(a[0])를 꺼내 배열 마지막 요소(a[9])와 바꾼다. 이러면 a[9]은 정렬된 상태가 된다.

	{1,9,5,8,3,2,4,6,7,10}
    a[0] ↔ a[9] 교환 완료 (a[9]는 정렬 완료)

B

앞과정에서 힙의 루트를 빼 왔으니 힙이 풀렸을 것이므로, 다시 힙으로 만들어준다.
다시 만들어진 힙에서 루트(a[0])를 정렬이 안된 배열의 마지막 요소(a[8])와 바꾼다. 이러면 a[8] ~ a[9]은 정렬된 상태이다.

    {9,8,5,7,3,2,4,6,1,10}
    다시 힙으로 만들어 줌.

	{1,8,5,7,3,2,4,6,9,10}
    a[0] ↔ a[8] 교환 완료 (a[8]~a[9]는 정렬 완료)

C

앞과정에서 힙의 루트르 빼 왔으니 힙이 풀렸을 것이므로, 다시 힙으로 만들어준다.
다시 만들어진 힙에서 루트(a[0])를 정렬이 안된 배열의 마지막 요소(a[7])와 바꾼다. 이러면 a[7] ~ a[9]는 정렬된 상태다.

    {8,7,5,6,3,2,4,1,9,10}
    다시 힙으로 만들어 줌.

	{1,7,5,6,3,2,4,8,9,10}
    a[0] ↔ a[7] 교환 완료  (a[7]~a[9]는 정렬 완료)

위 과정 A,B,C을 반복하다 보면 배열을 힙을 활용해 정렬하는 힙정렬을 끝낸다.

위 과정을 간단히 정리하면 다음과 같다.

  1. 배열이 힙 상태가 아닐 수 있으니 배열을 힙 상태로 만든다.
  2. 변수 i(마지막 인덱스)값을 n(요솟수) - 1로 초기화 한다.
  3. a[0] 과 a[i]를 교환한다.
  4. a[0]~a[i-1]을 다시 힙으로 만든다.
  5. i값을 1 감소시켜 0이 되면 끝내고, 그렇지 않으면 '2'로 돌아간다.

자 알고리즘의 0단계인 배열을 힙 상태로 만드는것 부터 살펴보자.

배열을 힙으로 만들기

다음과 같은 이진트리가 있다고 하자. 4를 루트로 하는 부분트리(A박스)는 힙이 아니다. 그러나 4의 자식인 8과 5를 각각 루트로하는 부분트리(B,C박스)는 모두 힙이다.

앞에서 루트를 없앤 다음 마지막 요소를 루트로 옮기고, 루트로 옮긴 요소를 알맞은 위치로 내려보내며 힙을 만들었다. 여기서도 이 방법으로 루트 4를 알맞은 위치로 내려보내면서 부분트리 A를 힙으로 만들 수 있다.
아랫부분의 작은 부분트리부터 시작해 올라가는 방식(bottom-up)으로 전체 배열을 힙 상태로 만들 수 있다.


위 이진트리를 힙으로 바꾸는 과정을 살펴보자.
가장 아랫부분의 오른쪽 부분트리부터 시작해 왼쪽으로 진행하면서 부분트리를 힙으로 바꾼다. 가장 아랫부분의 단계가 끝나면 한칸위로 올라와 똑같이 오른쪽에서 왼쪽으로 진행하면서 부분트리를 힙으로 바꾼다. 이 과정을 반복하면 힙 상태로 바꿀 수 있다.

글로 이해하기 어렵다면 아래 그림과 설명들을 읽어보자

A

마지막 부분트리인 {9, 10}을 선택하고, 요소 9를 10과 교환해 힙 상태로 바꾼다. 해당 부분트리는 힙 상태가 되었다.

B

마지막-1번째 부분트리인 {7, 6, 8}을 선택하고, 힙 상태로 만들기 위해 7과8을 교환한다. 오른쪽 그림은 가장 아랫부분의 단계가 끝난 상태가 된다.

C

가장 아랫부분에서 한 칸 올라와 오른쪽에서 왼쪽으로 살펴본다. 요소{5, 2, 4}부터 검사해야 하는데, 이미 힙 상태이므로 그대로 놔 두고 왼쪽으로 옮겨서 살펴본다.

D

바로 왼쪽에 있는 3을 루트로 하는 부분트리를 선택후, 3을 오른쪽 아래로 내려 힙으로 만든다.

E

마지막으로 이진트리의 루트인1을 같은방법으로 자식들 중 큰수랑 바꿔가며 내리면 힙 상태가 된다.

예제 코드

위에서 살펴본 내용들을 바탕으로 프로그램을 작성해보자.

public class HeapSort {
    // 배열 요소 a[idx1]과 a[idx2]의 값을 교환한다.
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // a[left] ~ a[right]를 힙으로 만든다.
    static void downHeap(int[] a, int left, int right) {
        int temp = a[left]; // 루트
        int child;          // 큰 값을 갖는 자식
        int parent;         // 부모

        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; // 큰 쪽을 자식에 대입한다.
            if (temp >= a[child])
                break;
            a[parent] = a[child];
        }
        a[parent] = temp;
    }

    // 힙 정렬
    static void heapSort(int[] a) {
        int lng = a.length;
        for (int i = (lng - 1) / 2; i >= 0; i--) { // a[i] ~ a[lng-1]를 힙으로 만든다.
            downHeap(a, i, lng - 1);
        }
        for (int i = lng - 1; i > 0; i--) {
            swap(a, 0, i);                    // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환한다.
            downHeap(a, 0, i-1);              // a[0] ~ a[i-1]을 힙으로 만든다.
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("요솟수: ");
        int[] x = new int[sc.nextInt()];

        for (int i = 0; i < x.length; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = sc.nextInt();
        }

        heapSort(x); // 입력받은 배열으로 힙 정렬 수행.

        System.out.println("힙정렬 완료");
        for (int i = 0; i < x.length; i++) {
            System.out.println("x[" + i + "]= " + x[i]);
        }
    }
}

  • downHeap() 메서드
    배열 a에서 a[left] ~ a[right]의 요소를 힙으로 만드는 메서드이다. 맨 앞에 있는 a[left]이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만들어주는 로직이다.

  • heapSort() 메서드
    요솟수가 n개인 배열 a를 힙 정렬 하는 메서드이다. 다음과 같이 2단계로 구성된다.

    1. downHeap()을 통해 배열 a를 힙으로 만든다.
  1. 루트(a[0])에 있는 값을 꺼내 배열의 정렬되지 않은 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복하여 정렬을 수행한다.
profile
정순동
:D
이전 포스트

Arrays.sort로 퀵,병합 정렬하기

다음 포스트

도수 정렬

0개의 댓글