[Data Structure] Heap : Max Heap, Min Heap | 최대힙, 최소힙이란

Heap 은 만드는데 worst case로 O(n log n) 까지도 걸린다.

하지만 제일 큰값과 작은 값을 찾을 때는 O(1)이다. 

그리고 Heap sort는 inline sort를 (추가 배열 불필요) 할 수 있어서 아주 강력한 소팅 알고리즘이다.

 

Heap의 종류는 두가지가 있다 Max Heap과 Min Heap

 

Max Heap의 조건은 다음과 같다.

- 9는 root node이다. 

- 8과 7은 parent node인 9보다 작다

- 2와 3은 parent node인 8보다 작다

- 5와 6을 parent node인 7보다 작다.

 

 

 

 

 

Min heap 은 Max와 반대다. 자식이 부모보다 작아야함

 

012345678910

 

 

01234