자료구조. 최소힙, 최대힙, 힙정렬

최소, 최대힙에 대해 설명하기 전에

이진힙에 대해 설명을 하자면 

트리로 만든 Heap 인데 완전이진트리여야한다는 조건이 붙는다.

이진 힙을 List로 생성해보자

0	1	2	3	4	5	6	7	8	9
-	100	19	36	17	3	25	1	2	7

1번 째 줄은 Index, 두번 째 줄은 원소 값이다.

여기서 부모, 자식간의 관계를 수식으로 나타낼 수 있는데

1. a[i]의 자식은 a[2i], a[2i+1]에 존재한다. 2. a[j]의 부모는  a[j/2]에 존재한다.(소숫점은 버린다.)

위와 같은 공식이 나오게 된다.

최소힙

최소힙은 부모가 자식보다 더 작은 값을 지니는 힙을 말한다.

최대힙

최대힙은 부모가 자식보다 더 큰 값을 지니는 힙을 말한다.

위에 있는 사진이 최대힙이다.

힙정렬

힙정렬의 알고리즘을 보자면

1. 정렬되지 않은 n개의 데이터를 입력 받는다.

2. 해당 데이터를 최대힙으로 구성한다.

3. root를 다른 list의 맨 끝으로 뺀다.

2,3번 반복

시간 복잡도는 O(n log n)이다.