정렬 알고리즘 : 힙 정렬

1.힙 정렬

앞서 설명드린 버블정렬, 선택정렬, 삽입정렬은 구현이 비교적 쉬운 반면 성능은 좋지 못했습니다. 빅오만 봐도 O(n^2) 이니까요. 앞서 설명 드릴 힙 정렬, 병합정렬, 계수정렬, 기수정렬 들은 조금 복잡해 보일 수도 있지만 성능이 좋은 정렬 들입니다. 우선 오늘은 힙 정렬에 대해서 자세히 알아보겠습니다.

 

---

1.1. 힙 정렬 : 이해와 구현

---

우선 힙 정렬을 이해하려면 힙이 무엇인지 알아야 합니다.

힙이란 엉덩이를 뜻하는 것이 아니라, 트리의 한 종류입니다. 트리가 무엇인지 잘 모르시는 분들은 이 글을 참고하시기 바랍니다. 

http://wogh8732.tistory.com/2?category=672741

힙은 완전 이진 트리로 두 가지 부류로 나뉩니다. 

---

     최대 힙

 

최대 힙은 위와 같이 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리킵니다.

---

---

        최소 힙

최소 힙은 위와 같이 루트 노드로 올라갈수록 저장된 값이 작아지는, 즉 루트 노드의 값이 제일 작고 아래로 내려갈수록 값이 커지는 완전 이진 트리를 가리킵니다.

---

그리고 힙은 완전 이진트리 구조이기 때문에 부모 자식 간의 관계를 구하기가 쉽습니다. 

왜냐하면 왼쪽 노드부터 차례대로 채워지는 것이 완전 이진 트리이기 때문이죠. 따라서 부모-자식 간의 관계를 정리하면 다음과 같습니다.

 

---

1. 부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2

2. 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2

3. 오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2 + 1

---

 

이제 힙 정렬의 전체 흐름을 살펴보죠. 진짜 이해하기 쉽게 설명하겠습니다. 우선 정렬 되지 않은 숫자들이 쭉 나열되어 있습니다. 5 3 2 4 1 이렇게 말이죠.

저는 오름차순으로 정렬을 해야 하기 때문에 최소 힙 기준으로 설명 드리겠습니다. 표시되는 값이 우선순위를 뜻 한다 가정하고 값이 작을수록 우선순위가 더 높은 것입니다. 

우선순위가 1인게 제일 높겠죠? 그리고 코드의 구현을 쫌 더 쉽게 하기 위해 노드의 인덱스를 0부터가 아닌 1부터 시작하겠습니다.

 

총 과정을 2개로 설명 드리겠습니다.

---

1). 힙에 데이터 삽입하기

처음에는 데이터가 아무것도 없으므로 인덱스 1에 바로 삽입합니다. 

완전 이진 트리이기 때문에 좌측부터 차례대로 값을 삽입합니다. 

인덱스 2에 값을 대입하고 최소 힙 구조를 완성 시켜야 하기 때문에 부모 노드의 값과 비교를 합니다. 

3보다 5가 크므로 스왑 해줍니다.

이번엔 인덱스 3에 2를 대입해줍니다. 

 부모 노드와 값을 비교합니다. 2가 더 작은 값이므로 부모 노드와 스왑 해줍니다.

그 다음 인덱스 4에 값을 삽입합니다.

삽입한 값의 부모 노드와 비교를 합니다. 

4가 더 작은 값이므로 스왑 해줍니다. 

그럼 인덱스 2로 올라갑니다. 

한번 더 부모 노드와 값을 비교합니다. 

이번에는 부모 노드의 값이 더 작으므로 그대로 위치합니다.

마지막으로 1을 인덱스 5에 삽입합니다.

부모 노드와 비교를 합니다. 1이 더 작은 값이므로 스왑 해줍니다.

한 번 더 부모 노드 2와 비교합니다. 1이 더 큰 작은 값 이므로 부모 노드와 스왑 해줍니다.

         이렇게 최소 힙 의 구성을 갖췄습니다.

---

자 위 그림을 보면 루트 노드의 값이 가장 작은 최소 힙 입니다. 즉 루트 노드의 우선순위가 가장 높은 것이지요. 

따라서 루트 노드의 값을 차례대로 빼면 오름차순으로 정렬된 데이터가 나오게 됩니다. 

단 여기서 루트 노드를 삭제하면 그 자리가 비기 때문에 그 자리를 최소 힙 구성에 맞게 다시 채워주는 과정을 거쳐야 합니다. 

이제 그 과정에 대해서 다시 설명 드리겠습니다.

---

2) 힙에서 데이터 삭제하기

루트 노드인 1을 삭제한 뒤 배열에 저장합니다. 

2-2 맨 마지막 노드를 루트 노드에 올립니다.

이러한 과정을 거치는 이유는 루트 노드를 삭제하면 빈 자리를 매꿔야 하기 때문에 마지막 노드를 루트 노드의 자리로 옮긴 다음에 자식 노드와의 비교를 통해서 제자리를 찾아가게 해야 합니다.

그럼 이제 4를 자식 노드와 비교합니다.

 

1. 두 자식 노드의 우선순위를 먼저 비교합니다. 그럼 2의 우선순위가 더 크기 때문에 2가 선택됩니다.

2. 선택된 2와 루트 노드의 값과 비교를 합니다. 2가 더 우선순위가 높으므로 스왑 해줍니다.

 3. 4의 자식 노드인 5와 비교를 합니다.. 이번에는 4가 더 우선순위가 높으므로 변경 없습니다.

2-3 루트 노드를 삭제한 뒤 배열에 저장합니다.

마지막 노드를 루트 노드로 올리고 아까와 같은 과정을 반복합니다.

1. 루트노드의 두 자식노드의 우선순위를 먼저 비교합니다. 그럼 3의 우선순위가 더 크기 때문에 3가 선택됩니다.

 2. 선택된 3과 루트 노드의 값과 비교를 합니다. 3이 더 우선순위가 높으므로 스왑 해줍니다. 

2-5 루트 노드를 삭제한 뒤 배열에 저장합니다.

2-6 마지막 노드를 루트 노드로 올립니다.

 자식 노드와 비교를 합니다. 자식 노드인 4가 우선순위가 높으므로 스왑 해줍니다.

더 이상 해줄 것이 없으므로 루트 노드를 삭제한 뒤 다시 배열에 넣습니다.

마지막으로 5를 루트 노드에 올리고 더 이상 비교 할 것이 없으므로 바로 삭제한 뒤 배열에 저장합니다.

---

---

1.2 힙 정렬 성능 평가

---

비교연산의 횟수를 근거로 하여 힙의 데이터 저장 및 삭제의 시간 복잡도는 다음과 같습니다.

힙의 데이터 저장 시간 복잡도 : O(log(2)n)

힙의 데이터 삭제 시간 복잡도 : O(log(2)n)

 

삽입과 삭제를 하나의 연산으로 묶는다면 시간복잡도는 다음과 같습니다

O(2log(2)n)

하지만 숫자 2는 빅오에서 무시할만한 수준이므로 삽입과 삭제를 하나의 연산으로 묶는다 해도 이 연산에 대한 시간복잡도는 다음과 같습니다.

O(log(2)n)

그럼 정렬과정에 대한 시간 복잡도는 어떻게 될까? 정렬대상의 수가 n개라면 총 n개의 데이터를 삽입 및 삭제해야 하므로 위의 빅오에 n을 곱해야 합니다.

O(nlog(2)n)

전에 설명한 빅오O(n^2)와 비교를 해보겠습니다.

결과적으로 위의 표에서 보이듯이 nlog(2)n과 n^2는 큰 차이가 있습니다.