[알고리즘] 히프 정렬 heap sort

히프 정렬 알고리즘

• 주요 특징
  • 최대 히프(Max Heap) 구조의 특성을 최대한 활용
    • 최대 히프 구조는 특정 조건을 만족하는 이진 트리
      1. 부모 노드의 값은 자식 노드보다 작지 않음
      2. 레벨 최소
    • 결과적으로 루트 노드가 가장 큰 값을 가짐
  • 최대 히프 구조를 계속 재구성하면서, 루트 노드를 한번에 하나씩 차례대로 추출하는 방식으로 정렬
• 복잡도분석
  • 최대 히프 구조 초기 생성 : O(n log n)
  • 최대 히프 재구성 : 매회 최대 O(log n), 총 n-1회
  • 전체 비교 회수 : O(n log n)
• 장단점 
  • 수행 시간 아주 우수, O(n log n)
  • 추가 기억공간 불필요 (cf) 2원 합병 정렬, 2n

 

void Heap_Sorting(data A[], int n) {
	int i, j; 
    data temp;

	// 최대 히프 구조 생성
	for (i = n/2; i > 0; i--) { 
    	Max_heap(A, i, n);
	}        

	// 실제 정렬
	for(i = n-1; i > 0; i--) {
		// 두 원소 A[1], A[i+1] 교환
		swap(A[1], A[i+1], temp);
		Max_heap(A, 1, i); 
	}
}

 

히프 정렬을 활용한 예제

#include <iostream>
using namespace std;

const int SIZE = 15;
int L[SIZE] = { 10, 4, 7, 1, -2, 12, 28, 66, 9, 3, 5, 7, 6, 21, 11 };


void print_data()
{
	for (int i = 0; i < SIZE; i++)
		cout << " " << L[i] << " ";
	cout << endl;
}

void max_heap(int L[], int SIZE, int i)
{
	int largest = i; 
	int l = 2 * i + 1; 
	int r = 2 * i + 2; 

	if (l < SIZE && L[l] > L[largest])
		largest = l;

	if (r < SIZE && L[r] > L[largest])
		largest = r;

	if (largest != i)
	{
		swap(L[i], L[largest]);

		max_heap(L, SIZE, largest);
	}
}

void heap_sort(int L[], int SIZE)
{
	for (int i = SIZE / 2 - 1; i >= 0; i--)
		max_heap(L, SIZE, i);

	for (int i = SIZE - 1; i >= 0; i--)
	{
		swap(L[0], L[i]);
		max_heap(L, i, 0);
	}
}

void main()
{
	cout << "Input Data : ";
	print_data();

	heap_sort(L, SIZE);

	cout << "\n\nSorted Data : ";
	print_data();

}