[정렬 알고리즘] - Heap Sort

먼저 우선순위 큐를 알아야한다. 우선순위 큐는 사실 가장 일반적인 큐이다. 왜냐하면 스택이나 큐도 우선순위 큐를 사용하여 구현할 수 있기 때문이다. 적절한 우선순위만 부여하면 우선순위 큐는 스택이나 큐로 동작할 것이다.

 

우선순위 큐는 네트워크 트래픽 제어, OS에서 작업 스케쥴링 등에 사용된다. 이러한 우선순위 큐를 구현하기 위해 사용되는 자료구조가 배열, 연결 리스트 등으로 구현이 가능한데, 가장 효율적인 구조는 Heap 을 사용한 방식이다.

 

이제 Heap에 대해 알아보자! heap 이란 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리로 최대값, 최소값을 찾아내는데 유용하다. 이러한 힙 정렬을 사용할때 가장 좋은 경우는 전체 자료를 모두 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할때이다.

최대힙과 최소힙으로 나눠질수있다. 최대힙은 각 노드의 키 값이 그 자식노드보다 크거나 같고 최소힙은 각 노드의 키 값이 그 자식노드보다 같거나 작다.

• 최대 힙 : key(부모노드) ≥ key(자식노드)
• 최소 힙 : key(부모노드) ≤ key(자식노드)

구현

(업로드 예정입니다!)

시간 복잡도 분석

Heap의 삽입 연산과 삭제 연산의 시간 복잡도를 계산해보자.

 

삽입 연산에서는 새로운 노드의 키 값이 자신의 부모 노드 키 값보다 작아질 때까지 서로 위치를 바꾸는 작업을 반복한다. 이때 최악의 경우 루트 노드까지 올라가는 경우이므로 트리의 depth에 해당하는 비교연산과 이동연산이 필요하다. heap은 완전이진 트리이므로 높이가 $log_2N$이 되고 따라서 $O(log_2N)$의 시간 복잡도를 가지게 된다.

 

삭제 연산에서는 마지막 노드를 루트로 가져온다음에 자식 노드들과 비교하는 연산이 가장 시간이 오래 걸리게 된다. 이때 최악의 경우 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이만큼 시간이 걸린다. 따라서 $O(log_2N)$의 시간 복잡도를 가지게 된다.