2-0) [C]힙(Heap)

1) 힙이란?

힙이라는 데이터 구조를 사용하여 정렬하는데, 최소값이나 최대값을 찾는데 최적화되어있는 완전이진트리 형태의 자료구조이다.

 

1. 힙에 모든 숫자를 내림차순으로 저장

2) 힙의 시간복잡도

삽입정렬에서는 각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교한다. 만약 왼쪽에 있는 숫자가 작다면 교체가 발생하지 않고 라운드를 종료한다.

하지만 꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때는 그 숫자가 가장 왼쪽에 도착할 때까지 비교와 교체 작업을 한다. k라운드에서는 k-1회씩 작업한다. 따라서 최악의 경우에는 2라운드에서 1회, 3라운드에서 2회, ..., n라운드에서 n-1회의 비교와 교체가 발생하므로 계산 시간이 버블 정렬이나 선택 정렬과 같이  O(n^2)이다. 그리고 최악의 입력 데이터는 마찬가지로 역순으로 나열된 경우이다.

 

3) 힙 구현

#include <stdio.h>

int main(void){
  int data[6] = {5, 2, 3, 6, 4, 1};
  int keyValue;
  int j;
  printf("Before sorting :\n");
  
  for(int i =0; i<6;i++){
    printf("%d",data[i]);
  }
  printf("\n");
  for(int i=0; i<5;i++){ 
      keyValue=data[i+1];
      for(j=i;j>=0;j--){ //keyValue 앞의 숫자들 확인
          if(data[j]>keyValue){ 
              data[j+1]=data[j];
          }
          else{
              break;
          }
        }
        data[j+1]=keyValue;
    } 
        
  printf("After sorting :\n");
  for(int i=0; i<6;i++){
      printf("%d",data[i]);
  }
  
  return 0;
  }

결과화면

Before sorting :
523641
After sorting :
123456