힙 정렬(Heap Sort)

힙 정렬은 분할 정복 알고리즘의 대표 격인 병합 정렬과 퀵 정렬만큼 빠른 알고리즘이다. 힙 정렬은 힙 트리 구조를 활용한 정렬 기법을 말한다. 여기서 힙은 완전 이진 트리로 구성된 구조인데, 완전 이진 트리(Complete Binary Tree)는 이진 트리 중에서도 트리의 노드가 중간에 빈 곳없이 모두 채워져 있는 이진 트리를 말한다.

 

완전 이진 트리이면서 힙의 특성을 갖고 있는 것을 힙이라고 하는데, 이 특성은 부모 노드가 자식 노드보다 무조건 크거나 작은 특성을 말한다. 최소 힙은 부모가 항상 자식 노드보다 작은 값을 가진 힙이고 최대 힙은 부모 노드가 항상 자식 노드보다 큰 값을 가진 힙이다. 다만 자식 노드들끼리는 대소 관계가 정해지지 않는다.

 

오름차순 정렬을 구현한다고 했을 때 우리는 최대 힙을 이용해서 구현해보겠다. 

 

---

 

[7 ,5, 9, 3, 0, 2, 1, 6, 4, 8]

이 데이터를 우선 완전 이진트리 구조로 만든 후, 최대 힙 구조로 만든다. 완전 이진 트리 구조는 배열로 표현이 가능한데, 중간에 빈 곳이 없는 완전 이진트리를 구성하기 때문에 인덱스를 붙여 트리를 만들어보면 다음과 같다. 트리에서 루트에 가까울 수록 인덱스가 0(시작)에 가깝고 루트에서 멀어질 수록 인덱스가 커진다.

 

 

완전 이진 트리

 

정리 되지 않은 데이터를 힙 구조로 만드는 것을 heapify(힙 생성 알고리즘) 라고 하는데 데이터의 각 노드에 대하여 heapify를 수행하면  부모 보다 큰 값을 가진 자식 노드는 부모와 자리를 바꾸게 된다. 이 때 부모와 바꾸는 자식 노드는 둘 중에 더 큰 값이다.  그렇게 모든 노드에 대하여 heapify 연산이 수행되면 힙 구조가 된다.

이 때 주의해야할 점은 루트와 먼 곳에서(맨 뒷 노드) 부터 차례대로 heapify 연산을 해야한다는 것이다. 그래야 아랫부분에 있는 큰 값들을 차례로 위로 끌어올릴 수 있기 때문이다. 그림을 보자.

 

맨 뒷 노드인 8에서 연산을 수행.

 

제일 뒷 노드인 8에서부터 heapify 연산을 적용해보자. 이 연산은 '하나의 노드'에 대해서 수행하는 것인데, 8을 부모노드라하고 자식 노드들을 살펴보고 더 큰 값이 있는지 살펴본다. 근데 자식 노드가 없다. 따라서 자식 노드가 없는 노드에 대해서는 연산을 하지 않아도 된다. 그말은 그 앞의 숫자인 2, 1, 6, 4, 8은 차례로 모두 heapify를 할 필요가 없다. 왜냐 그 앞의 노드들에서 수행해주어서 자리가 바뀔테니 문제가 없다.

 

그럼 인덱스 9에서 부터 8, 7, ... 을 넘어 바로 자식 노드가 있는 0(인덱스 4)으로 넘어가보자

 

8과 0의 자리가 바뀜

 

인덱스 4에 있는 부모노드인 0은 유일한 자식노드인 8보다 작다. 즉 자식노드가 더 크기 때문에 둘의 자리를 바꾼다.

그럼 이제 8의 인덱스가 4이다. 위치를 바꾼다음에는 부모노드가 바꾼 자식노드가 되는데 (0이 부모노드가 된다) 부모노드의 자식이 있다면 또 한번 자식 노드와 비교해서 자리를 교환해야한다. 하지만, 현재 0에는 자식노드가 없기 때문에 heapify가 끝나게 된다.

 

인덱스 4에 대해서 연산을 수행했으므로 3에 대해 수행할 차례다. 

 

 

3과 6의 자리가 바뀜.

 

 3(인덱스도 3)의 자식은 6과 4가 있는데 큰 값이 더 위 레벨에 위치해야하니 6을 골라서 부모노드인 3과 비교한다. 자식인 6이 더 크기 때문에 6이 위로 올라가게된다. 마찬가지로 부모노드인 3의 자식이 있는지 다시 한번 확인해보니 없다. 여기서 heapify 연산을 마치게 된다.

 

이렇게 각 노드에 대해서 heapify를 거치게 된다면, 최대 힙이 완성되고 데이터는 다음과 같다.

 

최대힙

부모노드는 항상 자식노드에 비해 크다. 최대힙이 되었는데, 힙의 특성은 만족하지만 정렬이 안되어있다. 이제 최대 힙에 대해서 정렬을 수행해야한다.

 

정렬의 순서는 다음과 같다.

1. root 노드를 제일 뒤의 값과 자리를 바꾸고
2. 바뀐 루트노드 에 대해서 heapify를 수행하여 다음으로 큰 값을 루트로 올라오게 한다.
3. 여기서 제일 뒤로 보낸 루트 값은 정렬이 완료된 것이므로 이 부분을 제외하고 1, 2를 계속 진행한다.

9와 1을 바꾸었고, 9는 정렬이 되었다.

루트 였던 9를 제일 뒤에있던 1과 바꾸었고, 그러면 9는 이제 정렬이 완료된 것으로 취급하고 표시를 해둔다. 이를 제외하고 heapify를 루트 노트에 실행하면 8이 루트로 올라온다.

 

루트가 8

다시 8을 제일 뒤로 보내고 8을 제외한 heapify를 하면

 

왼쪽 그림 처럼되고, 정렬 작업을 반복하고나면 오른쪽 트리와 같이 데이터가 정렬된다. 

데이터를 반대로 정렬하고 싶다면 최소 힙을 활용하면 된다.

 

힙 정렬 알고리즘의 복잡도는 N * logN이고, 정렬을 위해 추가적인 공간을 필요로 하지 않는 다는 점에서 효율적이다.

 

 heapify 는 한번 트리의 깊이를 내려갈 때마다 데이터의 갯수가 2배씩 늘어난다. 따라서 1024개의 데이터가 있다고 가정했을 때 한번의 heapify는 logN인 10번만 수행해도 완료된다. 그리고 각 노드에 대해서 heapify 를 수행해야 하므로 N * log N의 시간복잡도가 나온다고 볼 수 있다. 힙 정렬 알고리즘은 퀵 정렬, 병합 정렬 알고리즘 처럼 N * log N의 성능을 가지지만 단순 속도로는 퀵정렬 만큼 빠르지는 않는다고 한다. 

경험상 다익스트라 알고리즘에서 데이터의 수가 압도적으로 많을 경우에 쓰면 매우 효율적인 것 같았다. 

 

코드로 구현해 본다면 다음과 같다. 

 

힙정렬

참조

https://m.blog.naver.com/ndb796/221228342808

10. 힙 정렬(Heap Sort)

틀린 부분이 있다면 지적 부탁드립니다