Heap Sort 정렬 알고리즘 ( 개념 / 시간복잡도 -O(nlogn) )

안녕하세요!! 오늘은 힙정렬에 대해 공부해봅시다 ㅎㅎ

자.. 일단 힙이래요.

힙이 뭘까요? Heap?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 

완전이진트리(Complete binary tree)를 기본으로 한 자료구조.

출처 -위키백과-

저는 이렇게 기억해요. 

힙은 두가지 조건을 만족하는 자료구조다.

1. 구조조건 - 완전이진트리

2. 순서조건 - Partial Order를 만족한다.

완전이진트리를 여기에서 설명은 하지 않겠습니다. 

검색하시면 바로 알 수 있어요!!

추가로 앞으로 설명할 완전이진트리는 left 완전이진 트리라는 것만

알아두세요!

그리고 순서조건으로 넘어가서

Partial Order..?이게 뭘까요?

반댓말은 total Order입니다. 

total Order의 예시로는 정렬된 시퀀스(sorted sequence)라 할 수 있어요.

순서조건이 모든 원소에 대해 만족하죠?

하지만 Partial Order는 아닙니다. 

"Partial Order는 데이터의 일부분에 대해서 어떠한 특성을 만족하는 것"

이라고 할 수 있습니다. 

그럼 어떻게 "순서조건"을 만족할까요? 

힙에는 두가지 종류가 있습니다. 

부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙'

 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부릅니다. 

하지만 total Order를 만족하지 못하는 이유는 위 조건이 "직계관계"에서만 만족한다는 것이죠. 

힙 구조에서 어떤 키 값에 대해 레벨은 위지만(depth가 작지만) 현재 이 노드의 키값보다 키값이 작을 수 있다는 것입니다.

그래서 Partial Order에요.

아니 힙정렬 알려달라니까;; 왜 힙을 설명;;;;;

ㅎㅎ..꼭 알아야해요!!

힙을 알아야 힙정렬을 이해할 수 있는 것은 당연하겠죠?

이제..힙도 알았으니 진짜 힙정렬을 하러 가봅시다. 

자.. 정말 중요한 이야기가 하나 있는데요.

보통 입력이 배열로 주어진다는 것은 다들 아실겁니다. 

어떤 배열 딱 던져주고

정렬해~~~

보통 이러죠?

완전이진트리를 배열로 구현했을 때 정말 좋은 장점이 하나가 있죠. 

인덱스로 접근이 "바로" 가능하다는 것이죠.

자. 완전이진트리를 한번 볼까요?

주어진 배열로 완전이진트리를 만들면 위 트리모양이 되겠죠?

이때 엄청나게 유용한 장점이 생기게 되는데, 

한 노드를 알면 그노드의 부모 또는 자식들을 인덱스로 바로 접근이 가능합니다.

(흰색은 데이터고, 빨간색은 인덱스입니다.)

노드 i의 부모 노드 인덱스 :   i/2, (단, i > 1)

노드 i의 왼쪽 자식 노드 인덱스 : 2 x i

노드 i의 오른쪽 자식 노드 인덱스 : (2 x i) + 1

자, 한번 해볼까요? 

3을 가지고 한번 해보자구요.

3의 인덱스는 현재 "3"이네요.

3의 부모를 알고싶어요.

그럼 3의 인덱스인 3을 2로 나누어주면 1.5죠?

소수는 버려주기 때문에 즉, "1의 인덱스가 3의 부모다" 라는것을 알게됩니다. 

인덱스1의 데이터는 6이죠? 이렇게 3의 부모는 6이라는 것을 알게됩니다.

자식을 찾아볼까요?

현재 3의 인덱스인 3에 x2를 하면 6이 나옵니다. 즉 인덱스 6(=5)이 3의 왼쪽자식임을 알 수 있습니다. 

현재 3의 인덱스인 3에 x2+1을 하면 7이 나오죠?  즉 인덱스 7(=7)이 3의 오른쪽자식임을 알 수 있습니다. 

이때문에 인덱스 1부터 시작한다는 것도 알 수 있겠네요.

결국!!!제가 하고싶은 말은!!!!!!!!!!!!!!!

만약 입력이 크기 n인 배열로 주어진다.

==

크기가 n인 완전이진트리를 하나 준다.

==

힙의 구조조건을 만족한다.

그러므로 만약 입력이 배열이라면, 힙의 구조조건을 따로 만족해줄 필요없이

순서조건만 만족시켜주면 된답니다.

완전이진트리는 이제 됐는데..순서조건은 어떻게 맞추냐!!

그건 최대힙(max-heap), 최소힙(min-heap)에 따라 다릅니다. 

일단 저는 최대힙으로 배웠기 때문에 최대힙으로 설명드릴게요!

최대힙을 할 줄 아신다면 자연스럽게 최소힙방법도 아실거에요.

자, 순서조건은 어떻게 만족시킨다구요?

네 바로 Partial Order를 만족하면 된답니다. 

최대힙에서의 "직계관계"에서는 무조건 내 부모는 나보다 키값이 커야합니다.

자연스럽게 자식들은 부모모다 키값이 작겠죠? 

아..계속 힙정렬 알려달라니까 ㅡㅡ 힙이야기만 하고있네

...

이제부터 진짜하겠습니다.

일단 "힙정렬"을 하려면 다른 정렬 알고리즘처럼 그냥 하면 안됩니다. 

그럼 뭐 해야하냐?

1단계 : 주어진 배열을 최대힙/최소힙으로 만든다. (이번 예제에서는 최대힙으로 만들겁니다.)

2단계: delete를 통해 정렬을 한다. 

그럼 1단계를 해봅시다. 

(1단계 : 주어진 배열을 최대힙/최소힙으로 만든다. (이번 예제에서는 최대힙으로 만들겁니다.)

일단 정렬이 필요한 데이터들이 아무렇게나 섞여있겠죠? 아무런 순서도 없이 말이죠.

예를들어

이러한 데이터가 있다고 생각해볼게요.

일단 힙으로 만들어볼까요? 힙은 "완전이진트리"라고 했죠?

하지만 배열로 n크기의 인풋이 주어졌으니,  

이를 만족하는 완전이진트리는 단 하나입니다.

즉, 힙의 2가지 조건 중, 구조조건을 만족하게 되는 것이죠.

일단 완전이진트리로 그려볼까요?

빨간색 - 인덱스 / 검정색 - 데이터

자.. 위의 완전이진트리는 (의도치 않게 포화(full)이진트리가 됐네요.) 최대힙일까요?

Partial Order이므로 아무 부분트리나 잡아도 부모의 키값은 두 자식의 키값보다 커야합니다. 

즉, 최대힙의 순서조건을 만족해야합니다.

위 완전이진트리는 순서조건을 만족하고있나요?

아니죠.

루트노트부터 그 조건을 만족시키지 못합니다.

 정렬을 하기 위해서 우리는 위 완전이진트리를 최대힙/최소힙으로 만들어주어야 합니다. 

만드는 방법은 간단해요. 

왼쪽 밑에서 부터 봅니다. 

자, 우리는 최대힙으로 만들어줘야한다는 것을 잊지마세요.

최대힙 -  부모가 자식보다 키값이 커야한다!!(부모의 키값 > 자식들의 키값)

하지만 딱 봐도 부모보다 자식의 키값이 더 크네요. (부모의 키값 < 자식들의 키값)

그럼 어떻게 만들어주면 될까요?

네. 7,15,14중 최댓값인 15가 올라가면 (부모가 되면) 7,14보다 커지게 되므로

순서조건을 만족하게 됩니다. 

밑의 시간복잡도 계산에서 이해하셔야 할 게 하나 있어서

말씀드리자면,

이 7은,  2번의 비교과정을 거치게 됩니다.

15와 한번, 14와 한번.

7은 그 중 큰값과 자리를 바꾸게되죠.

만약 7이 두 자식보다 크다면, 7은 그 자리를 계속 유지하게 됩니다. 

15를 부모로 만들어볼까요? 

자, 15가 위로 올라감으로써 부모의 키값이 자식들의 키값보다 커지게 되었죠?

그러므로 이 부분트리는 순서조건을 만족하게 됩니다. 

하지만 이 부분트리만 순서조건을 만족하면 안됩니다. 모든 부분트리가 최대힙의 순서조건을 만족해야 해요.

다음 부분트리로 넘어가 볼까요? 

자. 이제 딱 보이시죠?

일단 순서조건을 만족하지 않습니다.

그럼 뭐가 부모로 올라가야할까요~~

네. 12입니다. 올려보죠

이 최대힙으로 만드는 과정은 재귀로 이루어지기 때문에,

다음 과정은 11,8,6으로 이루어진 부분트리가 아니라

이때까지 처리했던 두 부분트리의 부모인 3을 포함한 부분트리가 이번에 처리할 트리가 됩니다. 

자 일단 3은 두 자식들보다 작으므로 

15와 12중 큰 15가 올라가게 됩니다. 

여기서 끝난걸까요?

아닙니다.

자, 3이 내려간 부분트리를 봐주세요. 

3

7    14

3이 내려옴으로써 이 부분트리의 순서조건이 만족하지 않게 됩니다.

그럼 어떻게 해주면될까요?

네. 그냥 한번 더 해주면 됩니다. 

7과 14중 큰 값인 14가 3보다 크므로

3의 자리에 가게 됩니다. 

자. 이제 저 빨간 세모안에 있는 모든 (부분)트리는 순서조건을 만족하게 됩니다. 

즉, 모든 부분 트리의 "직계관계"에서 부모의 키값이 자식의 키값보다 크죠.

자 이제 어디쪽으로 갈까요?

네. 오른쪽 부분트리로 갈 차례입니다. 

자, 한번 봅시다.

순서조건을 만족하나요?

네. 웬일로 순서조건을 만족하네요. 11이 8,6,보다 크니까요!

다음으로 넘어갑시다. 

역시 이 트리도 순서조건을 만족합니다.

다음으로 넘어가죠

자. 딱 봐도 순서조건을 만족하지 않습니다.

이젠 다 할 줄 아시죠?!

부모인 5가 자식인 11과 13보다 작기때문에 자식중 큰 값인, 즉 13과 자리를 바꾸어줘야 합니다. 

자, 이제 순서조건이 다 만족됐나요? 네. 빨간색 세모 안에 있는 모든 부분트리가 순서조건을 만족합니다.

 이제 뭘 하면 될까요? 네. 이제 전체 트리를 검사할 시간입니다. 

자. 이제 너무 쉬울지경이네요.

1이 15,13보다 작으니 13과 15의 최댓값인 15가 1의 자리로 가야합니다. 

하지만 1이 내려간 부분트리에서도 순서조건이 만족하지 않게 됩니다.

그럼 14가 올라와야겠죠?

역시 1이 내려감으로써 순서조건이 만족하지 않게 됩니다.

그럼 7이 위로 올라가야겠죠.

자. 1이 leaf까지 내려오게 되었네요.

이제 모든 부분트리들이 순서조건을 만족한다는 것을 볼 수 있죠?

이제 최대힙을 만드는 과정. 즉 힙정렬의 1단계가 끝나게 되었습니다. 

이렇게 만들어진 트리를 배열로 나타내면, 

이렇게 나타나게 되겠죠?

여기서 한가지 알고가면 좋은점은, 가장 처음 트리에서 1은 루트노드에 있었지만, 최대힙을 만들고나니 leaf까지 내려왔죠?

즉, 어떤 노드는 최대힙을 만드는 과정에서 leaf까지 내려올 수 있으므로 최악의 경우 O(트리의 높이)만큼 내려올 수 있습니다. 

이때의 최악의 경우는 루트노드에 있는 노드가 leaf까지 내려왔을 경우겠죠? 

완전이진트리에서 높이는 logn에 바운드되게 되므로

즉 O(logn)만큼 내려올 수 있습니다.

자!!!!!이렇게 최대힙 만드는 과정이 끝나게 되었습니다. 

이제 2단계로 넘어가야할 시간이네요.

2단계: delete를 통해 정렬을 한다. 

자. delete?이게뭘까요? 뭘 지우는 걸까요?

우리가 최대힙을 왜!!! 만들었을까요?

네. 최대값을 쉽게 얻을 수 있기 때문이죠.

부분트리에서 계속 최대값을 부모로 올리면서 완전한 트리까지 해나갔죠?

그럼 최종적으로 트리의 루트노드에는 뭐가 올까요?

네. 배열안에서 가장 큰 데이터가 루트노드로 오게됩니다. 

이건 자명한 사실이에요.

(최소힙은 배열안에서 가장 작은 데이터가 루트노드로 오게 되겠죠?)

그럼 우리는 이 루트노드를 지우는(delete) 방법을 통해 정렬을 진행해보려고 합니다.

진짜로 2단계를 진행해봅시다.

이 2단계를 쉽게 이해하기 위해서 다시 작은 단계들로 쪼개어 볼게요.

2.1단계 - 맨 마지막 노드와 루트노드를 교환한다.

2.2단계 - 현재 루트노드에 대해  다운힙(순서조건을 만족하게 하도록 만드는과정)을 진행한다. 

사실 2.1단계는 이 힙정렬이 in-place냐 아니냐에 따라 다릅니다.

만약 정렬이 완성될 배열을 따로 두게되면, 

루트노드는 지워준뒤, 이 완성될 배열의 맨 뒤에 넣어주고

트리의 가장 마지막 노드를 루트노드에 넣어줍니다.

하지만 힙정렬은 in-place정렬이 가능한 정렬알고리즘이에요.

가장 마지막이 루트노드로 가게되면 가장마지막에 있는 자리(인덱스)는 비게되겠죠?

그 자리에 가장 큰 데이터인 루트노트가 들어가도 아무 문제 없다는 말입니다.

in-place로 설명드릴게요.

2.1단계 : 루트노드와 가장 마지막노드의 자리를 바꾸어준다. 

자. 그러면 배열안에서 가장 큰 데이터인 15가 맨 뒤에 가게 되겠죠. 

이 15는 정렬이 끝났다고 생각해도 무방합니다. 

그냥 노드가 "없다"라고 생각하세요. 마지막노드에 루트노드가 간 순간, 저 노드는 이제 우리가 비교할 비교대상에서 사라진다고 보면 됩니다. 

정렬을 큰 순서부터 뒤에서부터 채워간다고 생각하시면 돼요.

2가 루트노드에 오게 되었습니다.

2.2단계 : 현재 루트노드에 대해  다운힙(순서조건을 만족하게 하도록 만드는과정)을 진행한다. 

2가 루트노드에 옴으로써 순서조건이 어떻게됐나요?

네. 만족하지 않게 되었습니다.

그럼 이 2를 내려(down)줘야해요.

그래서 다운힙이라고 부른답니다.

이 2를 자기자리를 찾아가도록 해줘봅시다.

이 과정은 아까 최대힙으로 만드는 과정과 완벽하게 똑같습니다.

어려워하지마세요.

2와 2의 자식들인 14와 13을 비교합니다. 가장 큰 14와 2를 바꾸어줍니다. 

자. 2가 내려감으로써 순서조건이 모든 부분트리에 대해 만족하나요?

네. 아닙니다. 역시 2의 자식들이 2보다 크므로

다운힙을 계속 진행해주어야겠네요.

7과 12중 큰값인 12와 2를 교환해줍니다. 

역시나...또 순서조건이 만족하지않죠.

자. 이렇게 순서조건을 만족하도록 다운힙을 진행해줬습니다. 

이제 뭘하면 되냐구요?

이 2단계(2.1단계, 2.2단계)를 계속~~~진행해주시면 됩니다. 

이걸 다 ㅠㅠㅠㅠ 이 글 안에서 하지는 못할것 같아요. 너무너무 길어지기 때문이죠..

제가 데이터가 7개인 배열로 했다면...다 할 수 있었을텐데

그냥 크기가 커지면 못하시는 분들이 계실까봐

15개 했어요. 이 15개를 할 줄 알면 7개는 완벽하게 하실 수 있을테니까요!

어쨌든 너무 길어지긴했는데, 이 글에 못쓰는 대신 제가 동영상으로 준비를 해봤어요. 

이 예제를 최대힙으로 만드는과정과, 정렬을 끝내는 과정까지 담아놨으니 

참고하시기 바랍니다 :)

궁금한 점이 있다면, 언제든지 질문해주세요.

위 단계를 계속 진행하면 마지막엔, 

이렇게 정렬이 되게 됩니다.

자. 이제 시간복잡도 이야기를 해보죠.

일단 최대힙으로 만드는 과정을 생각해봅시다. 

이 과정은 O(n)입니다.

그리고 DownHeap과정은 한 노드에 대해 logn만큼 내려갈 수 있댔죠?

하지만 내려가면서 2번의 비교를 진행하므로

2logn입니다.

즉, n개의 데이터에 대해 2logn번의 비교를 진행하면서

즉 2nlogn번의 비교연산을 진행하게 됩니다.

즉, 힙정렬의 시간복잡도는 

2nlogn+n입니다.

즉, 빅오노테이션으로 표현하면

O(nlogn).

힙정렬은 최악의 경우에도 O(nlogn)정렬 알고리즘임을 잊지마세요!

또한 힙정렬도 분할정복(Divide and Conquer)알고리즘입니다.

근데 찾아보니 이 힙정렬을 분할정복이라고 보지않는 견해도 많네요.

하지만, 힙 구성 과정에서 

이런식으로 최대힙을 만들어가죠?

이 부분에서 분할정복 기법을 쓴 것 같다고 하더라구요.  

이렇게 힙정렬하는 방법이 끝났습니다!!!!

XD

궁금한점은 댓글로 물어봐주세요.

도움이 되었으면 좋겠어요 💕