19. 힙(Heap) 정렬 알고리즘

1. 개요

 우선순위 큐의 특징을 살린 알고리즘.

 한번의 삽입, 삭제 과정이 이론적으로 O(logn)의 시간이 걸림.

 전체 데이터 삽입, 삭제 과정은 이론적으로 O(nlogn)의 시간이 걸림.

 힙 정렬은 힙 내부에서 정렬되는 속성을 이용.

 알고리즘은 단순히 데이터 전체를 힙에다 넣었다가 빼는 과정.

 그러므로 O(nlogn)+O(nlogn) = O(2nlogn) => O(nlogn)

 힙(우선순위큐)에 대한 설명이 아님.

 이번 코드는 STL 라이브러리의 우선순위큐 사용. 하지만 속도가 버블 정렬보다 느림. (추후 직접 구성하여 비교해봐야 함)

2. 코드

2-1) 메인

2-2) 힙(우선순위큐) 정렬 알고리즘

2-3) 출력

3. 해설

 C++의 STL 라이브러리의 우선순위큐를 이용해서 정렬시켰지만 그 속도가 현재 버블 정렬보다 느리다. 

 데이터가 10000개 이상일 시 시간이 5분이 걸려도 계산을 끝마치지 못했다.

 힙 정렬을 하려면 STL 라이브러리 사용않고 직접 힙을 구성해야 할 듯하다.

 기억해야할 것

 (1) 그냥 병합 정렬이나 퀵 정렬 쓰는 것이 낫다.

 (2) 그러나 우선순위큐의 원리는 알아야한다. (추후 작성)