[정렬] 6. 힙 정렬

힙 정렬

: 기본 아이디어는 버블 정렬과 비슷하다. 

  1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내며 정렬한다.

  버블 정렬과 다른 점은, 버블 정렬은 남은 원소에서 1등을 다시 비교를 통해 찾아야 하지만

  힙 정렬은 힙(Heap)을 이용하면, 1등을 뽑아낸 뒤, 나머지 원소에서 1등을 뽑을 때 다시 비교할 필요 없이 2등이 자동으로 1등이 된다.

 

그럼, 힙(Heap)에 대해 잠깐 알아보자.

힙의 성질

1. 리프 노드를 제외한 모든 노드는 자식이 반드시 2명

2. Max heap: 부모는 자식보다 반드시 크다. Min heap: 부모는 자식보다 반드시 작다.

 

Min heap, Max heap( 출처: https://guides.codepath.com/compsci/Heaps )

 

힙의 삽입과 삭제 (출처: https://guides.codepath.com/compsci/Heaps)

자, 이제 힙 정렬에 대해 본격적으로 들어가보자.

우선 다음과 같은 큰 줄기를 가진다.

" Heapify(힙으로 만들기) " -> " 정렬"

백문이 불여일Run [3, 5, 7, 9, 4, 2]를 정렬해보자.

 

1) Heapify

 

2) 정렬

 

루트 노드에 있는 원소가 최대값이므로 해당 원소를 가져와 리스트의 가장 마지막 인덱스에 삽입한다.

 

위와 같은 과정을 반복하며 정렬을 완성한다.

 

이와 동일한 과정을 배열로 표현한 과정도 같이 참고해서 이해해보자. 

(출처: https://www.youtube.com/watch?v=gB7qYgikT1Y)

 

시간 복잡도

: O(nlogn)