힙 정렬(Heap Sort) 알고리즘

ssuda·2020년 1월 7일
0

힙 정렬(Heap Sort) 알고리즘


  • 힙 정렬 알고리즘이란?
    최소 힙 트리(내림 차순 정렬)나 최대 힙 트리(오름 차순 정렬)를 구성해 한번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤에서부터 저장한다.
  • 힙 이란?
    노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리 형태인 완전 이진 트리의 일종으로 최솟값이나 최댓값을 빠르게 찾아내도록 만들어진 자료구조이다.
    부모의 키 값이 자식의 키 값보다 항상 크거나(작거나) 같은 이진트리를 말한다.
    • 힙의 삽입
      새로운 노드를 힙의 마지막 노드에 삽입하고, 새로운 노드를 부모 노드들과 교환하여 힙의 성질을 만족시킨다.
    • 힙의 삭제
      루트 노드를 삭제하고, 루트 노드에 마지막 노드를 가져온다. 현재 루트 노드와 자식 노드들과 교환하여 힙의 성질을 만족시킨다.

힙 정렬의 시간 복잡도


힙은 완전 이진 트리로 높이는 log n이기 때문에 하나의 요소를 힙에 삽입하거나 삭제할 때 θ(log n)의 시간 복잡도를 갖는다.
힙 정렬 알고리즘에서는 n개의 요소로 힙에 삽입하여 힙을 구성한 뒤에 n개의 요소를 힙에서 삭제하므로 총 θ(n log n)의 시간 복잡도를 갖는다.

즉, n크기의 데이터에 대한 이진탐색 알고리즘의 시간복잡도는 다음과 같다.
T(n) = θ(n log n)

힙 정렬 알고리즘의 장점과 단점


  • 힙 정렬 알고리즘의 장점
    - 최악의 경우에도 시간 복잡도인 θ(nlogn)을 보장한다.
    • 가장 큰 값 몇 개만 필요할 때 힙정렬 알고리즘이 유용하다.
  • 힙 정렬 알고리즘의 단점
    - 데이터들의 상태에 따라 다른 정렬법들에 비해서 조금 느린편이다.
    - 데이터의 순서가 바뀌는 unstable한 알고리즘이다.

힙 정렬 알고리즘의 구현


  • 핵심 코드
void heapify(int* data_arr, int data_size, int i) {
	int largest = i;
	int left_child = 2 * i +1 ;
	int right_child = 2 * i +2;

	if (left_child<data_size && data_arr[left_child]>data_arr[largest])
		largest = left_child;
	if (right_child<data_size && data_arr[right_child]>data_arr[largest])
		largest = right_cild;

	if (largest != i) {
		swap(data_arr[i], data_arr[largest]);
		heapify(data_arr, data_size, largest);
	}
}
void build_heap(int* data_arr, int data_size) {
	for(int i = data_size / 2-1; i >= 0; i--)
		heapify(data_arr, data_size, i);
}
void heap_sort(int* data_arr, int data_size) {
	build_heap(data_arr, data_size);

	for (int i = data_size-1; i >= 0; i--) {
		swap(&data_arr[0], &data_arr[i]);
		heapify(data_arr, i, 0);
	}
}

참고 자료


정렬별 장단점 및 시간 복잡도
완전이진트리(Complete Binary Tree)란? - 준수의_개발정리노트
자료구조 힙이란? - heejeong Kwon

profile
안녕하세요 코딩을 사랑하는 ssuda 입니다.

0개의 댓글