Heap Sorting에 관해

2020-04-19

Heap Sorting

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

Heap Sorting 절차

정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.

내림차순또는 오름차순을 기준으로 정렬

그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.

삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

장점

시간 복잡도가 좋은편

힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 이다.

시간복잡도

힙 트리의 전체 높이가 거의 log₂n(완전 이진 트리이므로)이므로

하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log₂n만큼 소요된다.

요소의 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 걸린다.

T(n) = O(nlog₂n)


public class HeapSort {
	private static void heapSort(int[] arr)// 기능1
	{
		int n = arr.length;

		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i);
		}

		for (int i = n - 1; i > 0; i--) {
			swap(arr, 0, i);
			heapify(arr, i, 0);
		}
	}

	private static void heapify(int[] arr, int n, int i)// 기능2
	{
		int p = i;
		int l = i * 2 + 1;
		int r = i * 2 + 2;

		if (l < n && arr[p] < arr[l]) {
			p = l;
		}

		if (r < n && arr[p] < arr[r]) {
			p = r;
		}
		/* 최대
		if (l < n && arr[p] > arr[l]) {
			p = l;
		}
		if (r < n && arr[p] > arr[r]) {
			p = r;
		}*/

		if (i != p) {
			swap(arr, p, i);
			heapify(arr, n, p);
		}
	}

	private static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	private static void printArray(int[] arr) {
		for (int data : arr) {
			System.out.print(data + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] arr = { 3, 9, 4, 7, 5, 0, 1 };
		printArray(arr);
		heapSort(arr);
		printArray(arr);
	}
}