Heap에는 min heap, max heap이 있다.
이에 대한 정의는 위키피디아!
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
힙 (자료 구조) - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최
ko.wikipedia.org
위키피디아 짱..!
아무튼 가장 쉽게 heap sort를 생각할 수 있는 방법은
i) min heap이 있으면 root 원소를 pop한 후 배열에 넣는다
ii) heapify한 후 i반복한다.
시간복잡도를 살펴보면
| # of elements | n | n-1 | n-2 | ... | 1 |
| time | lg(n) | lg(n-1) | lg(n-2) | ... | lg(1) |
따라서 lg(n!)이 나오는데 lg(n!) < nlg(n)이므로
시간복잡도는 nlg(n)이라고 할 수 있다.
하지만 문제점이 있다! 바로 in-place가 아니라는 점이다.
(추가적인 배열이 필요하다)
in-place로 구현하려면 어떻게 해야 할까?
Q. 모든 원소가 똑같을 때 theta(n)이지만, n-5개는 같고 5개는 다른 값일 때 시간복잡도는 어떻게 될까?
'[알고리즘개론] - Algorithm > [Concept]' 카테고리의 다른 글
| Prim's Algorithm (Time Complexity) (0) | 2020.11.13 |
|---|---|
| Prim's 알고리즘 (0) | 2020.11.13 |
| BinaryHeap time Check (0) | 2020.10.23 |
| 알고리즘 Find_Max (0) | 2020.10.20 |
| 시간측정 (0) | 2020.10.17 |
