힙 정렬(Heap Sort)

힙 정렬
힙 트리 구조(Heap Tree Structure) 를 이용하는 정렬 방법

병합 정렬(Merge Sort)와 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘

 

힙이란?

최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

최대힙이란?

'부모 노드'가 '자식 노드'보다 큰 힙

 

최대 힙

 

자기 자신 노드의 자식이 되는 노드들이 자신보다 작다.

 

만약에,

 

어떤 노드의 경우가 최대 힙의 조건을 만족하지 않아,
최대 힙이 되지 않을 경우 힙 정렬을 수행하는데
이때 힙 생성 알고리즘(Heapify Algorithm) 을 사용한다.

힙 생성 알고리즘은 특정한 '하나의 노드'에 대해서 수행하는 것
또한 해당 '하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태'라고 가정을 한다는 특징이 있다.
위에 트리에서 5만 힙 정렬을 수행해주면 전체 트리가 최대 힙 구조로 형성되는 상태이다.

특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.

위에 트리에서는 5와 자신의 값보다 큰 자식인 7과 위치를 바꿔주므로써
힙을 유지할 수 있게 된다.

또한 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우,
또 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다.
자식이 더 이상 존재하지 않을 때까지 한다.

힙 생성 알고리즘의 시간 복잡도는 한번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다는 점에서 O(logN)이다.
예를 들어 데이터의 갯수가 1024개라면 대략 10번 정도만 내려가도 된다.

 

 

---

 

기본적으로 완전 이진 트리를 표현하는 가장 쉬운 방법은 배열에 그대로 삽입하는 것이다.
현재 정렬할 데이터의 갯수가 9개이기 때문에 인덱스 0부터 8까지 차례대로 담아준다.

 

말 그대로 배열에 있는 인덱스가 차례대로 트리로 표현된 것이다.
완전 이진 트리를 배열로 표현하고, 배열을 다시 완전 이진 트리로 표현할 수 있어야 한다.

 

 

이 상황에서 모든 원소를 기준으로 힙 생성 알고리즘을 적용하여 전체 트리를 힙 구조로 만들어주어야 한다.
이 때 데이터의 갯수가 N개 이므로 전체 트리를 힙 구조로 만드는 복잡도는 O(N*logN)이다.
사실상 모든 데이터를 기준으로 힙 생성 알고리즘을 쓰지 않아도 되기 때문에 O(N)에 가까운 속도를 낼 수 있다.

 

 

 

O(N*logN)으로 이렇게 우리가 원했던 최대 힙을 구성할 수 있다.
이제 실제로 우리가 원하는 정렬을 직관적으로 수행할 수 있다.

루트(Root)에 있는 값을 가장 뒤쪽으로 보내면서 힙 트리의 크기를 1씩 빼준다.

 

 

위와 같이 9와 6을 바꾼 뒤에 9는 정렬이 완료된 것이므로 빨간색 처리를 한다.
이제 9를 제외하고 나머지 8개 원소를 기준으로 또 힙 생성 알고리즘(Heapify)를 수행한다.

 

 

 

이제 다시 가장 큰 숫자인 8이 루트에 존재하게 된다.
이것을 가장 뒤 쪽의 원소와 서로 바꾼다.

 

8과 9가 가장 뒤에 배열되어 정렬이 이루어졌다. 이 과정을 반복하면 된다.
힙 생성 알고리즘의 시간 복잡도는 O(logN)이고 전체 데이터의 갯수가 N개 이므로 시간 복잡도는 O(N*logN)이다.
또한 맨 처음에 힙 구조를 만드는 복잡도는 O(N*logN)이다.
따라서 전체 힙 정렬의 전체 시간 복잡도는 O(N*logN)이다.