Hear Sort

Heap은 1. Complete Binary Tree  2. Max heap property 혹은 minimum heap property를 만족해야 한다

cf ) Complete Binary Tree란 이진 트리의 맨 마지막 층을 제외하고는 노드가 꽉 차있으며 맨 마지막 층의 경우, 오른쪽 혹은 왼쪽 방향부터 노드가 삽입되어 있다. 

Heap Sort의 시간 복잡도 :

Heap을 n/2번 만들어야됨 -> Heap 만드는데 log(n) 따라서 Heap Sort의 시간 복잡도는 O(N*logN) 이다.

 

Heap을 활용해 우선순위 Queue를 만들기도 한다. 

Insert할 때의 시간 복잡도는 log(N)이고 

Extract할 때는 extract한 후에 heapify를 다시 해줘야되서 시간 복잡도는 log(N)이다.