6-8장 힙 정렬

1. 힙 정의하기 

 

힙(heap)

- '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리 

- 힙의 가장 위쪽에 있는 루트가 가장 큰 값이 됨

- 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함

- 형제 사이의 대소 관계는 일정하지 않음

 

완전 이진트리 

- 완전 : 부모는 자식을 왼쪽부터 추가하는 모양을 유지

- 이진 : 부모가 가질 수 있는 자식의 개수는 최대 2개 

 

 1) 부모는 a[(i-1)/2]

 2) 왼쪽 자식은 a[i*2+1]

 3) 오른쪽 자식은 a[i*2+2]

 

 

2. 힙 정렬 알아보기 

 

- '가장 큰 값이 루트에 위치'하는 특징을 이용 

- 선택 정렬을 응용한 알고리즘

 

- 1) 힙에서 가장 큰 값인 루트를 꺼냄

  2) 루트 이외의 부분을 힙으로 전환

 

-  힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해 

 나머지 요소로 만든 트리도 힙의 형태로 유지할 수 있도록 재구성

 

2.1 루트를 없애고 힙 상태 유지하기 

 

- 루트를 없앤 다음 다시 힙을 만들기 위해 요소를 알맞은 위치로 보내기

 1) 루트를 꺼냄

 2) 마지막 요소를 루트로 이동

 3) 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복

 이때 자식의 값이 작거나 잎에 다다르면 작업이 종료 

 

ex)

 - 힙에서 루트인 10을 꺼냄

 - 비어 있는 루트 위치로 힙의 마지막 요소 (오른쪽 아래 끝에 있는 자식 요소)인 1을 옮김

 - 1 이외의 요소는 힙 상태를 유지하고 있음 

 

- 루트를 이동시킨 1을 올바른 위치로 보냄

- 현재 자식들 {9,5}중 큰값인 9와 교환

 

- 현재 자식 중 {8,3}중 큰 값인 8과 교환

 

- 1의 두 자식 {6,7}중 큰 값인 7과 교환

- 1을 트리의 가장 아랫 부분으로 이동시켰으니 작업을 끝냄

 

2.2 힙 정렬 알고리즘으로 확장하기 

 

- 배열의 요소 개수 n

1) 변수 i값을 n-1로 초기화 

2) a[0]과 a[i]를 바꿈

3) a[0],a[1],..,a[i-1]을 힙으로 만듬

4) i값을 1씩 줄여 0이 되면 끝이 남. 그렇지 않으면 2)로 돌아감

 

ex)

- 힙의 루트(a[0])에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꿈

- a[9]는 정렬을 마치게 됨 

- a[0]~a[8]의 요소를 힙으로 만듬. 그 결과 두번째로 큰 요소인 9가 루트에 위치하게 됨

- 힙의 루트 a[0]에 있는 가장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꿈

- a[8]~ a[9]는 정렬을 마치게 됨 

 

- a[0]~a[7]의 요소를 힙으로 만듬

- 세 번째로 큰 요소인 8이 루트에 위치하게 됨 

- 힙의 루트 a[0]에 있는 가장 큰 값인 8을 꺼내 아직 정렬하지 않은 마지막 요소인 a[7]과 바꿈

 

 

3. 배열로 힙 만들기 

 

- 아랫 부분의 작은 부분트리부터 시작해 올라가는 방식 (bottom-up)으로 전체 배열을 힙으로 만들 수 있음

- 가장 아랫 부분의 오른쪽 부분트리부터 시작해 왼쪽으로 진행하면서 힙으로 만듬

- 가장 아랫 부분의 단계가 끝나면 하나 위쪽으로 부분트리 범위를 확장하고 다시 왼쪽으로 진행하면서 부분트리를 힙으로 만듬

 

- 힙 정렬 프로그램

//힙 정렬 프로그램 
#include <stdio.h> 
#include <stdlib.h>

#define swap(type,x,y) do { type t=x; x=y; y=t;} while(0)

//a[left] ~ a[right]를 힙으로 만드는 함수 
static void downheap (int a[], int left, int right) 
{
	int temp = a[left]; //루트
	int child;
	int parent;
	for(parent = left; parent < (right+1)/2; parent=child) {
		int cl = parent *2+1; //왼쪽 자식  
		int cr = cl+1; //오른쪽 자식  
		child = (cr <= right && a[cr] > a[cl]) ? cr : cl; //큰 값을 선택
		if(temp >= a[child]) 
			break;
		a[parent] = a[child];
	}
	a[parent] = temp;
}

//힙 정렬 함수 
void heapsort(int a[], int n) 
{
	for(int i = (n-1)/2; i >=0; i--)
		downheap(a,i,n-1);
	for(int i=n-1; i>0; i--) {
		swap(int, a[0],a[i]);
		downheap(a,0,i-1);
	}
}

int main()
{
	int nx;
	puts("힙 정렬:");
	printf("요소 개수:");
	scanf("%d",&nx);
	int*x=(int*)calloc(nx,sizeof(int));
	for(int i=0; i <nx; i++) {
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	heapsort(x,nx); //배열 x를 힙 정렬
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i <nx; i++) 
		printf("x[%d]=%d\n",i,x[i]);
	free(x); //배열 x를 해제 
	
	return 0; 
	
}