기본 알고리즘 - HeapSort

1. 개념

 

Heap Sort는 2가지 단계로 구성된다.

 

A. Build Heap

Heap 을 생성한다. 여기에서 사용하는 Heap 은 이진트리로서 가장 아래 층을 제외하고는 모든 노드가 채워져있다.

Heap 의 상위 노드를 채우는 방법에 따라 Max Heap, Min Heap으로 나뉜다.

오름차순으로 값을 정렬하기 위해서는 Max Heap을 사용하고 내림차순으로 정렬을 위해서는 Min Heap을 사용한다.

이유는 root node의 값을 빼서 가장 뒤로 보내고 다시 Heapify하기 때문이다.

 

B. Pop root node

root 노드의 값과 배열의 가장 끝 값을 교체한다.

노드를 교체한 다음에는 Heap이 깨졌으므로 다시 Heapify를 수행해서 Heap의 성질을 유지해야 한다.

 

C. 정렬

A,B 의 동작을 Heap의 크기가 1이 될 때까지 반복하면 Sorting이 완료된다.

 

 

2. 구현

 

public void privateSort(int[] A) {
		// TODO Auto-generated method stub
		int size = A.length; 
		
		buildHeap(A, size);
		
		while (size > 0)
		{
			swap(A, 0, size -1);
			--size;
			heapify(A,0,size);
		}
		
	}
	
	void buildHeap(int[]A, int n)
	{
		for (int idx = n/2 ; idx>= 0 ; idx--)
		{
			heapify(A,idx,n);
		}
	}
	
	// Max Heap
	void heapify(int[] A, int k, int n )
	{
		int left = 2*k; 
		int right = 2*k +1;
		int large = k; 
		
		if ( right < n )
		{
			// 2 children
			if ( A[large] < A [left]) large = left; 
			if ( A[large] < A [right]) large = right;
		} else if ( left < n )
		{
			if ( A[large] < A [left]) large = left;
		}
		
		swap(A, k, large); 
		
		if( large != k)
		{
			heapify(A,large,n);
		}
	}