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

힙 정렬

 

힙 정렬이란? - 힙의 특성을 이용한 정렬

 

수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place)

 

힙이란 ? - 완전 이진 트리에 가까운 형태

 

이진 트리란? - 각 노드의 자식수가 2이하인 경우

 

완전 이진 트리란 ? - Root(맨 위)노드부터 Leaf(가장 아래)노드까지 빠짐없이 채워져 있는 트리

 

여기서 root의 어원은 트리를 뒤집었을 때 가장 첫번째 . 뿌리라고하여 root라고 부른다.

 

완전 이진 트리의 조건은 왼쪽부터 차례로 채워야함.

 

만약                ㅇ

                     ㅇ ㅇ

                         ㅇ ㅇ

 

이렇게 있으면 왼쪽아래가 비어있다. 즉 왼쪽부터 차례로 채우지 않았기 때문에 완전이진트리가 아니다.

 

                      ㅇ

                  ㅇ      ㅇ

                ㅇ  ㅇ ㅇ  ㅇ

               ㅇㅇㅇ

 

이렇게 있으면 오른쪽아래는 비어있지만 왼쪽부터 채워져있기 때문에 완전이진트리이다.

 

 

이러한 완전이진트리를 엄밀하게 정의하는 이유는 트리를 배열에 넣었을 때 왼쪽부터 넣게 되는데 왼쪽이 비어있고 오른쪽만 있다면, 배열 중간에 빈 값 (Null)이 들어가기 때문에 엄밀히 정의한다.

 

 

힙 - Max-Heap , Min-Heap

 

 

Max-Heap : 부모 노드의 값은 항상 자식 노드의 값보다 크다. => 전체 트리의 Root 노드 값이 가장 크다.

 

즉 위(ROOT)로 올라갈수록(↑) 값이 커지는 트리

 

어떻게하면 배열이 주어졌을 때 최대 힙 (Max-Heap)을 만들 수 있을까?

 

 

 

Min-Heap : 자식 노드의 값은 항상 부모 노드의 값보다 크다. => 전체 트리의 Root 노드 값이 가장 작다.

 

즉 위(Root)로 올라갈수록(↑) 값이 작아지는 트리

 

어떻게하면 배열이 주어졌을 때 최소 힙 (Min-Heap)을 만들 수 있을까?

 

 

우선 힙은 우리가 형상화 시킨 모양이지 결국 배열에는 이런식으로 부모- 자식 , 왼쪽 자식(부모) -자식, 오른쪽 자식(부모) - 자식 순서

 

즉 왼쪽부터 차례대로 들어간다고 생각하면 된다.

 

 

힙을 배열에 저장하면 다음과 같이 검색이 가능하다.

 

i라는 노드의 부모값을 찾는 방법 

 

PARENT(i) : return [i/2]

 

i라는 노드의 왼쪽 자식값을 찾는 방법 

 

LEFT(i) return [2i]

 

i라는 노드의 오른쪽 자식값을 찾는 방법

RIGHT(i) [2i+1]

 

3번 노드의 왼쪽 자식을 찾는 법 : return 3*2, 6번 노드의 부모 찾는 법 : return 6/2 3번 노드의 오른쪽 자식을 찾는 법 : return (3*2)+1

 

 

노드의 높이는 현재 노드에서 leaf( 가장 아래) 노드까지 내려갈 때 가장 단순하게 내려가는 가장 긴 경로에서 (simple path) 거쳐야 하는 간선의 수이다.

 

16에서 2까지 3개의 노드를 거쳤기때문에 높이는 3이다.

 

Root 노드로부터 트리의 높이 : logN , Heap은 완전 이진 트리 구조를 가지기 때문에 각 레벨마다 노드의 수가 2배씩 증가하므로 높이는 logN ( N = 노드의 갯수 )

 

log10 = 3.xx

 

2의 3승은 =8 

2의 4승은 = 16

 

즉 높이는 최대 3

 

 

 

 

 

여기까지 힙에 대한 설명을 마치겠다.

 

그렇다면 임의의 완전이진트리가 있다. 이것을 Max-Heap 형태로 만들려면 어떻게 해야할까?

 

 

 

Max-Heapify : 어떠한 완전이진트리를 Max-Heap 형태로 만드는 것.         [전체 수행 시간 : LogN]

 

어떻게 만드는가? 부모와 자식을 비교, 자식이 부모보다 크면 자식과 부모를 바꾼다. 이 작업을 Root 부터 반복, 결국 부모는 항상 자식보다 크고, 자식은 부모보다 작다. Max-Heap 형태이다. 

 

 

부모와 자식을 비교, 교환함으로써 Max-Heap 형태를 만들었다.

 

 

#include<stdio.h>
#include<conio.h>
#include<math.h>
int parent(int i)
{
  return (i-1)/2;
}
int left(int i)
{
  return 2*i+1;
}
int right(int i)
{
  return 2*i+2;
}
void maxheapify(int arr[], int n, int i)
{
  int l, r,largest,temp;
  l = left(i);
  r = right(i);
  if(l<n && arr[l] > arr[i])
    largest = l;
  else
    largest = i;
  if(r<n && arr[r] > arr[largest])
    largest = r;
  //printf("\ni=%d  l=%d  r=%d largest=%d",i,l,r,largest);
  if(largest != i)
  {
    temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    maxheapify(arr,n,largest);
  }
}

void main()
{
  int arr[20];
  int i=0,n;
  clrscr();
  printf("Enter the the of element in array : ");
  scanf("%d",&n);
  printf("\nEnter the elements : ");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);

  printf("\n\tArray before max heap \n\n");
  for(i=0;i<n;i++)
    printf("%d ",arr[i]);

  for(i=(n-1)/2;i>=0;i--)
    maxheapify(arr,n,i);

  printf("\n\n\tArray after Maxheap \n\n");

  for(i=0;i<n;i++)
    printf("%d ",arr[i]);
  getch();
}

 

코드 출처 : http://programmingearth.com/post.php?pageid=80&title=C%20program%20to%20implement%20Max%20heap

C program to implement Max heap.

 

 

 

 

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