[ 힙 정렬 ( heap sort ) ]

• 힙은 완전 이진트리이며 우선순위 큐를 위하여 만들어진 자료구조임.
• 최악의 경우라도 시간 복잡도는 O(nlogn)을 보장.

힙 정렬의 시간 복잡도는 O(nlogn) 이다. 이유는 힙을 만드는 과정 O(logn)의 복잡도를 가지는데. 

n개의 원소를 모두 정렬 하기위한 최종적인 시간복잡도는 n * (logn) = O(nlogn) 이다

---

- 최소 힙

노드의 값이 1개씩인 힙이다.

1. (2) push.
2. (3) push 상위 노드가 3보다 작기 때문에 변화 없음.
3. (1) push 상위 노드가 1보다 크기 때문에 서로 위치 변경

 

 

다음은 아래의 문제를 풀 때 사용했던. push 되는 값이 2개인 경우이다.

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

값이 2개인 경우 앞의 번호순으로 먼저 정렬되고 만약 앞의 수가 같다면 뒤에 있는 숫자로 정렬된다.

 

 

 

결과

1. (2,9) push
2. (3,9) push 상위노드 값이 더 작기 떄문에 변화 없음.
3. (1,9) push 상위노드 값이 더 크기 떄문에 서로 위치 변경
4. (1,5) push 상위 노드의 값이 더 크기 때문에 서로 위치 변경
5. (1,5) 와 상위노드 (1,9) 의 첫 번째 숫자가 같지만 하위노드의 두 번째 숫자가 더 작으므로 위치 변경.
6. (2,11) push 상위 노드의 값이 더 작기 때문에 변화 없음