힙 정렬(Heap Sort)

힙정렬(Heap Sort)

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식

 

퀵정렬과 병합정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다. 하지만 힙 자료구조가 많이 활용되고 있는 것은 사실!

 

* 힙정렬 활용

 

1. 가장 크거나 가장 작은 값을 구할 때

최소힙 또는 최대힙의 루트값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다.

 

2. 최대 K만큼 떨어진 요소들을 정렬할 때

삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다. 

시간복잡도

■ heapify 함수 수행 시간

heapify 함수는 힙 구조를 만들기 위해 이진 트리에서 자식 노드와 순서를 바꾸는 재귀호출을 한다.

힙 이진 트리의 높이는 logN이다.

따라서 heapify 함수의 재귀호출 횟수는 logN이다.

따라서 heapify 함수의 수행 시간은 O(logN)이다.

 

■ buildHeap 함수 수행 시간

buildHeap 함수에는 N에 비례하는 for 루프가 있다.

이 for 루프에서 heapify 함수를 호출한다.

따라서 buildHeap 함수의 수행 시간은 O(NlogN)이다.

 

■ heapSort 함수 수행 시간

buildHeap 함수를 1회 호출한다.

heapify 함수를 N회 호출한다.

따라서 heapSort 함수의 수행 시간은 O(logN)이다.

 

평균	최선	최악
O(nlogn)	O(nlogn)	O(nlogn)

 

힙 정렬 과정

1. 최대(최소 힙)을 구성

2. 루트 노드는 가장 큰 값(가장 작은 값)이다. 마지막 요소와 바꾼 후, 힙의 사이즈 하나를 줄인다.

3. 바꾼 루트 노드의 값을 가지고 다시 최대(최소)힙 구조를 만들기 위해 heapify 함수를 호출한다.

 

 

루트 노드 11을 마지막 노드인 4와 바꾸고, 힙 사이즈를 -1 한 다음, 다시 최대 힙을 구성한다.

 

import java.util.Arrays;

public class 최대힙 {
	static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	// 힙 정렬 만들기
	static void buildHeap(int[] a) {
		int end = a.length-1;
		for(int i= end/2; i>0; --i) // 마지막 노드의 부모노드부터 거꾸로 Heap 조정 규칙 시작!
			heapify(a, i, end);
	}
	static void heapify(int[] a, int k, int end) {
		int left = 2*k, right = 2*k+1;
		int larger;
		// 왼쪽, 오른쪽 자식 노드 둘 다 있는 경우
		if(right <= end) {
			larger = (a[left] > a[right]) ? left : right;
		} else if(left <= end) larger = left; // 왼쪽 노드만 있는 경우
		else return; // 둘 다 없는 경우

		if(a[larger] > a[k]) { // 부모노드 a[k]보다 자식노드의 값이 더 클 때 swap한다.
			swap(a, larger, k);
			heapify(a, larger, end); // swap을 하고 다시 자식노드와 그 아래 자식 노드들 힙 조정 규칙
		}
	}

	// 가장 큰 값인 루트노드부터 이진 트리에서 제거한다.
	static void heapSort(int[] a) {
		buildHeap(a); // 최대힙의 구조로 만들기
		System.out.printf("최대힙 구조 : %s \n", Arrays.toString(a));
		for(int end=a.length-1; end>=1; --end) {
			swap(a, 0, end); // 마지막 노드와 루트 노드와 교환
			heapify(a, 0, end-1); // 제거한 노드를 빼고 다시 힙을 조정, end-1 주의! 배열 마지막 값부터 정렬
		}
	}

	public static void main(String[] args) {
		int[] a = {0, 3, 8, 2, 10, 4, 6, 7, 1, 9, 5};
		heapSort(a);
		System.out.printf("힙소트 : %s \n",(Arrays.toString(a)));
	}
}