[허언증/Algorithm] 힙정렬(Heap Sort)

안녕하세요 허언증입니다.

 

Heap Sort

 

 

힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리입니다. 힙에는 최대 힙과 최소 힙이 존재 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 경우 일 때. 일단 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 합니다.

 

 

6 => 부모 노드(root)

2,3 => 자식노드

 

 

부모노드의 값(6)이 자식노드(2,3) 보다 클 경우 그림 처럼 최 상단에 제일 큰 값이 있는 경우

 

 

 

 

 

 

2 => 부모 노드(root)

1,4 => 자식노드

 

현재의 경우에는 부모노드에 2가 있고 자식노드에 1,4가 있지만 4는 2보다 값이 더 크기 때문에 서로 교체를 해줘야 힙 형태가 된다. 이를 "힙 정렬"이라고 한다 

 

이진트리가 힙정렬이 완료가 되면 이제서야 오름차순,내림차순으로 정렬을 할 수 있습니다. 결국 힙정렬이 오름차순 내림차순을 하기 위해 꼭 필요한 전 단계라는걸 알고 계시면 됩니다!!

 

 

 

1. 이진트리를 힙정렬로 정렬한다!

2. 정렬이 된 상태에서 내림차순, 오름차순을 한다!

 

 

 

 

예시를 통해 좀 더 자세히 알아보도록 하자!!

 

기본 상태

부모노드(Root) : 6

6의 자식 노드 : 2,3

2의 자식 노드 : 1,4

 

제일 하단부터 힙정렬을 하고 상위로 올라가야 전체적으로 모두 힙정렬을 할 수 있기 때문에 1,2,4 쪽에서 부터 시작을 하도록 하겠습니다!

 

 

 

 

 

 

2가 부모 노드였지만 자식노드에 2보다 더 큰 수인 4가 있어서 서로 교환을 합니다. 그럼 정렬이 완료 된 상태가 됩니다. 전체적으로 힙정렬이 완료 되었기 때문에  "2. 정렬이 된 상태에서 내림차순, 오름차순을 한다!" 조건으로 제일 위에 있는 루트 노드를 제일 밑에 있는 곳과 위치를 교환 합니다! 이 때 위치를 교환 하는 이유는 정렬을 하기 위함이고 글을 계속 읽다 보시면 이해가 되실거에요.

 

 

 

 

현재는 6이 밑으로 이동 한걸 볼수 있습니다. 6은 정렬이 된 상태이고 이제 6을 제외한 1,2,3,4 범위만 체크를 해서 다시 힙정렬 형태로 만들도록 하겠습니다.

 

 

 

 

 

제일 하단인 1,2는 이미 힙정렬이 완료 된 상태이므로 제외하고 2,3,4를 정렬을 해야 하는데 2가 루트노드에 있고 그밑에 4가 있기 때문에 2와 4를 교환해 줍니다.

 

 

 

 

 

2와4를 교환이 완료가 되었다면 이진트리 전체가 힙정렬이 된 상태이므로 다시 루트노드 4와 제일 밑에 있는 노드인 1을 교환해 줍니다.

 

 

 

 

이젠 1,2,3만 다시 힙정렬을 해주면 됩니다. 4,6은 이미 정렬이 완료 된 상태이므로 힙정렬에서 제외합니다.

 

 

 

 

 

1,2,3 을 비교를 하는데 지금 같은경우 이미 정렬이 된상태이므로 3과1의 자리수를 교환합니다.

 

 

 

 

 

그럼 최종적으로 정렬이 된 걸 알 수 있습니다. 루트 노드에 1이 들어가고 2랑 교환을 한 상태에서 다시 정렬을 하게 되면 1,2 위 그림처럼 되기 때문에 해당 과정은 생략을 했습니다. 이해가 되지 않는다면 댓글남겨주세요 

 

 

이처럼 이진트리내에 있는 값들을 모두 힙 정렬을 맞춘 뒤 루트에 있는 값을 제일 하단으로 이동합니다. 하단으로 이동할 때 현재는 큰 값을 밑으로 내렸지만 작은값을 밑으로 내려도 상관 없습니다!

 

 

 

-코드-

 

Code 10~19

:힙정렬을 하는 코드 

 

12번째 코드 참고 

int root 변수를 선언 했는데 디버그를 직접 손으로 해 보면 위처럼 00 ,11, 22, 33 형식으로 나오는데 배열을 이용해서 이진트리를 구현했고 루트노드를 찾을 수 있는 하나의 수학 공식이라고 생각하면 되겠다.

 

 

Code 25~45

:힙정렬이 완료 된 상태에서 루트노드와 제일 하단에 있는 노드의 값을 교환하고, 교환 된 마지막 노드는 힙정렬 대상에서 제외를 해준다. (정렬이 완료 된 상태니까)