컴퓨터 알고리즘 초급 #6 ( 힙 정렬 in c ) 2

2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )

3산이 나오면 대피해야한다.

 

( 

 

힙 구조 만들기 (Building a heap)

 

BULID-MAX-HEAP(A)

 

A.heap-size = A.length

 

for i = [A.length / 2] downto 1

      MAX-HEAPIFY(A,i)

 

: 배열의 절반크기부터 자식과 부모를 비교하며 올라간다. 

 

배열의 절반부터 하는 이유 : n번째 부모는 2/n에 있다. 2/n보다 큰 부모는 없다. 가장 마지막에 있는 부모가 2/n이다.

 

 

 

10개의 숫자가 배열로 입력되었을 때 이진 트리의 표현 방법

 

A = {4,1,3,2,16,9,10,14,8,7}

 

A = A = {4,1,3,2,16,9,10,14,8,7}

 

2/10 = 5 (자식을 가지는 마지막 노드)

 

A[5] = 16 (자식을 가지는 마지막 노드)

 

16부터 시작하면된다.

 

부모 A[5]가 자식 A[10]보다 큰가? 맞으므로 그대로

 

A[4]가 자식 A[8]보다 큰가? 틀리다.

 

A[4]와 A[8]을 교환한다.

 

A[3]과 A[6],A[7]을 동일하게 비교

 

A[2]와 A[4],A[5]를 비교

 

A[1]와 A[2],A[3]을 비교

 

자식이 부모보다 크면 자식과 부모의 값을 교환한다.

 

결국 max-heap 구조를 만족하게 된다.

 

 

차례로 자식과 부모를 비교 -> 최종적으로 max-heap 구조 완성

 

여기서 중점은 자식을 가진 마지막 부모노드 (2/n)부터 (2/n)-1, 2/n-2 ... 2/n = 1이 될때까지 부모노드와 자식노드를 비교한 후 큰값을 점차 위로 올린다. (max-heapify 수행)

 

 

Max-heapify 수행시간 : logn 

 

전체 수행시간 : nlogn (2n부터 1까지 수행 즉 매번 logn번씩 2n번을 수행함. 전체수행시)

 

 

 

 

 

 

 

-------------------------------------------------------------------------------------------------------------------------

 

최대값 추출(Extract-Max)

 

Heap에서 가장 큰 값을 제거하고 Max-heap 구조는 유지시키는 연산

 

방법 : 가장 첫번째루트 A[1]와 가장 마지막루트 A[10]과 교체한다. 그 후 A[10]을 제거한다.

 

 

왼쪽은 A[1]과 A[10]을 교환한 후 A[10]을 제거하였다. 오른쪽은 Max-heapify연산을 통해 Max-heap형태로 다시 만들어주었다.

 

A[1]과 A[2],A[3]비교 A[1]<A[2] 이므로 값 교환. A[2]와 A[4],A[5] 비교 A[2]<A[4]이므로 값 교환 A[4]와 A[8],A[9] 비교 A[4]<A[9]이므로 값 교환

 

최종적으로 오른쪽 그림이 완성된다. (MAX-HEAP구조 완성)

 

수행시간은 logn

 

 

--------------------------------------------------------------------------------------------------------------

 

힙 정렬 (Heap Sort) 

 

HEAPSORT(A)

 

BUILD-MAX-HEAP(A)

for i = [A.length / 2 ] downto 2

exchange A[1] with A[i]

A.heap-size = A.heap-size -1

MAX-HEAPIFY(A,1)

 

 

root값을 배열의 맨 마지막으로 보냄. 그거의 힙사이즈를 동일하게 유지하면 보낸값이 다시 맨앞으로 올 것임 그걸 막기위해 (가장 큰값을 뽑을 때 마다 heap-size를 하나씩 줄여야 그 전까지만 비교하여 가장큰값이 맨처음으로 다시 돌아가지 않음)

 

가장 첫번째 값과 가장 마지막 값 교환 후 max-heapify

 

 

같은 과정을 계속해서 반복 ( 가장첫번째와 가장마지막값을 교환 )

 

 

결론: 힙정렬 알고리즘 이란 입력받은 숫자를 최대힙(최소힙) 구조로 만들고 현재 값 중에 가장 큰 값을 차례대로 뽑아내서 정렬문제를 해결하는 알고리즘이다.