알고리즘 [Algorithm] - 힙 정렬 Heap Sort(6) (C,Python)

힙정렬

이번에는 힙 정렬에 대해 알아보자. 힙정렬이란 힙트리 구조를 이용하는 정렬방법이다. 이를 이해하기 위해선 먼저 힙(Heap)구조를 알아야하고, 힙을 알기 이전에는 이진 트리(Binary Tree)에 대해 알아야 한다. 

 출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽자식 노트와 오른쪽 자식 노드 라고 한다.

(출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC)

 

완전 이진트리는 데이터가 루트(Root) 노드부터 시작해서 자식노드가 왼쪽 자식노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리이다. 즉 완전 이진트리는 이진트리의 노드가 중간에 비어있지 않고, 빽뺵하게 가득 찬 구조이다. 노드가 삽입될 때는 항상 왼쪽 자식노드부터 데이터가 들어간다.

 

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

 

힙 정렬을 수행하기 위해서는 힙 생성 알고리즘 (Heapify Algorithm)을 사용한다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해 수행하며, 해당되는 '하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태'라고 가정을 한다는 특징이 있다. 힙 생성 알고리즘 (Heapify Algorithm)이란 특정한 노드의 두 자식 중에서 더 큰 자식 노드와 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 뒤에도 자식노드가 존재한다면, 또 자식 중에서 더 큰 자식과 자신의 위치를 바꿔야 한다.  힙 생성 알고리즘의 시간 복잡도는 O(log N)이다.

 

 

---

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

7 6 5 8 3 5 1 9 6

---

 

#include <stdio.h>
#pragma warning(disable:4996)

int number = 9;
int heap[9] = { 7, 6, 5, 8, 3, 5, 9, 1, 6 };

int main(void) {	
	//힙을 구성
	//먼저 전체 트리 구조를 최대 힙 구조로 바꿉니다. (Heapify)
	for (int i = 1; i < number; i++) { // 전체 원소에 대해서 (1~8 -> 마지막 한개는 자동으로 되므로)
		int c = i; 
		do {
			int root = (c - 1) / 2; //특정한 원소의 부모 노드
			if (heap[root] < heap[c]) { //부모의 값보다 자식의 값이 더 크다면?
				int tmp = heap[root]; // 서로 자리를 바꿈
				heap[root] = heap[c];
				heap[c] = tmp;
				for (int i = 0; i < number; i++) {
					printf("%d ", heap[i]);
				}
				printf("\n");
			}
			c = root; //자식의 부모노드로 이동해서 반복적으로 수행
		} while (c != 0); // c가 root노드 (맨위)에 오게 되면 반복문 정지

	}
	

	//크기를 줄여가며 반복적으로 힙을 구성
	for (int i = number - 1; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp; //큰값을 뒤로 보내기
		int root = 0;
		int c = 1;
		do {
			c = 2 * root + 1;
			//자식중에 더 큰 값을 찾기
			if (heap[c] < heap[c + 1] && c < i - 1) {
				c++;
			}
			//루트보다 자식이 더 크다면 교환
			if (heap[root] < heap[c] && c < i) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
				for (int i = 0; i < number; i++) {
					printf("%d ", heap[i]);
				}
				printf("\n");
			}
			root = c;
		} while (c < i);
	}


}

완전 이진트리를 표현하는 가장 쉬운 방법은 배열을 이용하는 것이다. 현재 정렬할 데이터의 갯수가 9개이므로 index 0번부터 8번까지 차례대로 배열에 담으면 각 노드 번호에 해당하는 숫자가 들어갔다고 생각할 수 있다. 이후 힙 생성 알고리즘을 수행해 최대 힙 형태로 변환을 수행한다. 최대 힙 형태로 변환을 하게 되면 가장 큰 수가 root 노드에 온 걸 확인할 수 있는데, root에 있는 값을 가장 뒤쪽으로 보내고 힙 트리의 크기를 1씩 빼서 남은 원소들로 힙 생성 알고리즘을 수행한다. 이렇게 되면 가장 뒤쪽으로 보낸 원소는 고정되고 배열의 끝부터 큰 원소가 차례대로 정렬되게 된다.

 

  힙 생성 알고리즘의 시간 복잡도는 O(log N)이고, 전체 데이터의 갯수는 N개 이므로 힙 정렬의 전체 시간 복잡도는 O(N*log N)이라고 할 수 있다.

 

파이썬

n = 9
heap = [7,6,5,8,3,5,1,9,6]
for i in range(1,n): #최대 힙 구성
  c=i
  while(c!=0):
      root = int((c-1)/2)
      if heap[root]<heap[c]:
        tmp = heap[root]
        heap[root] = heap[c]
        heap[c] = tmp
        print(heap)
      c = root

print("*"*27)
print("*"*27)

for i in range(n-1,0,-1): #원소를 한개씩 줄이면서 힙 정렬 수행
  tmp = heap[0]
  heap[0] = heap[i]
  heap[i] = tmp

  root = 0
  c=1
  while True:
    c = 2*root+1
    if c>i : break
    if heap[c] < heap[c+1] and c < i-1:
      c+=1
    
    if heap[root] < heap [c] and c<i:
      tmp = heap[root]
      heap[root] = heap[c]
      heap[c] = tmp
      print(heap)
    root = c

heap

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz