힙 정렬(Heap-sort)

힙 정렬은 max-heap 또는 min-heap 자료구조를 이용하여 데이터를 효율적으로 정렬하는 정렬 알고리즘이다.

힙 정렬을 하기 전에 힙의 개념에 대해 간단히 살펴보자

힙(Heap)

1. 힙은 완전이진트리 구조를 갖는다.

2. 힙은 max-heap, min-heap 둘 중 하나의 특성을 가져야 한다.

완전이진트리를 배열로 구현 시 인덱스를 통해 부모 자식 노드에 바로 접근할 수 있다는 장점이 있다.

여기서 인덱스 0은 사용하지 않는다고 가정한다.

자신의 인덱스 i를 기준으로 왼쪽 자식노드의 인덱스는 i * 2, 오른쪽 자식노드의 인덱스는 (i*2)+1을 통해 바로 접근할 수 있다. 또한 자신의 부모노드는 i/2로 바로 접근할 수 있다.

위의 트리는 완전이진트리의 조건을 만족하지만 max-heap이나 min-heap의 특성을 만족하지는 않는다.

힙정렬을 하기 위해 우선 위의 완전이진트리를 max-heap 또는 min-heap으로 바꿔야 한다.

위의 트리는 max-heap이다 max-heap의 조건은 완전이진트리이며 부모노드가 자식노드보다 커야 한다. 

힙은 부모-자식 관계만 따지기 때문에 동일한 데이터에 대해 여러 개의 힙 구조가 나올 수 있다.

위의 트리에서 인덱스 4의 값이 3이 되고 인덱스 5의 값이 4가 되어도 문제가 없다는 뜻이다.

이제 위의 max-heap을 통해 heap정렬을 해보자.

max-heap이나 min-heap으로 만드는 이유는 최대값이나 최소값을 바로 얻을 수 있기 때문이다.

힙정렬은 delete 연산을 이용한다.

root 노드 값 삭제 -> 마지막 노드를 root로 가져옴 -> max-heap을 만족하도록 heapify 수행

이와 같은 과정을 반복한다.

삭제 연산은 O(1), heapify는 O(log n)이 걸린다. n개의 노드를 가지고 정렬해야 하므로 결과적으로 힙정렬의 시간복잡도는 이다.

아래 그림을 보자 삭제되는 값을 새로운 배열에 순차적으로 넣어도 되지만 여기선 기존에 있던 배열을 사용하고 검은색으로 나타내겠다.

즉, 검은색 노드는 삭제되었다고 생각하면 된다.

기존의 root였던 8을 삭제하고 마지막 노드인 1을 root로 가져왔다. 이제 다시 max-heap을 만족하도록 root노드를 down-heap 해야 한다.

자식노드인 7, 6 중에서 더 큰 7과 바꾼다. 

왼쪽, 오른쪽 자식 노드 중에서 더 큰 값과 비교하여 Downheap을 수행한다.

결과적으로 위와 같은 모습이 될 것이고 가장 큰 7이 root로 올라오게 된다.

Last 노드였던 2를 root로 옮기고 7을 삭제하였다.

이제 다시 max-heap이 되도록 2를 Downheap해야 한다.

2를 Downheap한 결과이다.

이제 root노드 6을 삭제하고 Last 노드인 2를 root로 옮길 것이다.

6은 삭제되었고 root노드인 2를 다시 Downheap해야 한다.

2를 Downheap한 결과이며 다시 max-heap이 되었다.

기존에 root였던 5를 삭제하고 Last였던 3을 root로 옮겼다.

이제 3을 Downheap해야 한다.

3을 Downheap한 결과이며 다시 max-heap이 되었다.

기존 root였던 4가 삭제되고 Last였던 1이 root로 올라왔다.

다시 1을 Downheap해야 한다.

1을 Downheap한 결과이며 다시 max-heap이 되었다.

기존 root였던 3이 삭제되고 Last였던 2가 root로 올라왔다.

max-heap을 만족하므로 2를 Downheap할 필요는 없다.

기존 root였던 2가 삭제되고 Last였던 1이 root로 올라왔다.

이제 노드가 하나 남았으므로 바로 삭제할 것이다.

최종결과는 다음과 같다.

max-heap을 통해 heap 정렬을 하니 데이터가 오름차순으로 잘 정렬되었다.(내림차순으로도 정렬할 수 있다.)