7-1 Heap sort - 동작방식(heapify)

이번에는 Heap Sort에 대해서 알아봅니다.

 

Heap을 Sorting 한다 인데, Heap 이라는 것이 무엇일까요?

 

이거는 아닙니다..

 

Heap이라는 애는 최댓값 및 최소값을 빨리 찾아내기 위해 고안된 완전이진트리 형태의 자료구조 입니다.

 

뭔가 말이 어려운데, 그냥 아래의 트리 같은 형태로 자료 쌓아놓고, 최대값이나 최소값 빨리 찾는 것입니다.

 

 

자, 그렇다면 동작 방법을 한번 알아볼까요?

 

이와 같은 배열이 있습니다.

 

[4, 10, 3, 5, 1]

 

얘를 이진 트리 형태로 만들어볼게요

 

왼쪽 오른쪽 왼쪽 오른쪽 이렇게 순서대로 배치했습니다.

 

 

그 다음 최대값을 찾아내는 과정을 진행해줘야 하는데, 이걸 heapify라고 합니다.

 

자, heapify가 어떻게 진행되는지 한번 보겠습니다.

 

가장 큰 애(최대값)이 맨 위로 올라와야 합니다.

 

그러면 지금 맨 위에 있는 애는 4입니다. 하지만 밑에 10이 있기 때문에, 4와 10을 체인지 해줍니다.

 

 

자 한번 바꿔줬습니다. 이제 배열이

 

[10, 4, 3, 5, 1] 이런 형태로 바뀌었습니다.

 

그 다음에는, 

 

자, 여기까지 하면 heapify가 완료되었습니다.

 

배열은 아래와 같이 완성되네요

 

[10, 5, 3, 4, 1] 

 

여기에서 마지막 것과 처음 것을 바꿔주고, 마지막 애를 지워줍니다.

 

 

 

자, 그 다음 1이 가장 큰 수가 아니기 때문에, 얘를 가지고 또 heapify 해줍니다.

 

 

자, 여기까지 하면 어느정도 정렬이 되었습니다.

 

또 1과 5를 변경해주고 5를 없애주고 또 다시 반복을 하겠죠?

 

이 과정을 반복해주면

 

[1, 3, 4, 5, 10]

 

이런 배열이 잘 나오는 것을 알 수 있습니다.

 

다음 시간에, 얘를 코딩해보고, 시간 복잡도를 알아보겠습니다.