우선순위 큐) 힙 정렬

§ 힙 (Heap)

: 내부노드에 키를 저장하면서 다음 두 가지 속성을 만족하는 이진트리

--> 우선순위 큐의 ADT 의 하나

1. 힙 순서: 모든 내부노드 v에 대하여 key(v) >= key(parent(v)) 을 만족 ( 반대도 성립한다 )

2. 완전이진트리

* 힙의 마지막 노드 : 높이를 h라 한다면, 깊이 h-1의 가장 오른쪽 내부노드

* 힙의 높이는 O(log n)이다. ~ 완전 이진트리의 경우

==> 완전 이진트리의 높이 증명     

깊이가 1인 경우 - 최소 노드 2개     < 2의 2제곱

깊이가 2인 경우 - 최소 노드 4개     < 2의 3제곱

...

깊이가 h-2        - 최소 노드 2의 h-2제곱       < 2의 h-1제곱

깊이가 h-1        - 최소 노드 2의 h-1제곱       < 2의 h제곱

노드의 숫자를 n이라 가정

그러므로  h의 높이는 O(log n) 임

§ 힙 정렬 (Heap Sort)

: 힙을 이용한 정렬

○ 힙 정렬은 두가지 방식으로 진행 가능

- 연결 리스트

- 순차 배열

- 성능 비교

	size / isEmpty	insert / remove	advanceLast / retreatLast	공간
연결	O(1)	O(log n)	O(log n)	O(n)
순차	O(1)	O(log n)	O(1)	O(n)