📚 Heap Sort

힙 정렬은 앞서 소개한 자료구조인 Heap의 성질을 이용해서 배열을 정렬하는 방법이다.
Heap의 Array representation을 봤을 때, 삭제 후에도 요소는 배열에 남아있지만 뒤에서부터 차곡차곡 쌓이게 된다.
이러한 성질을 이용해서 배열을 힙으로 만들고, 반복 삭제를 통해 정렬하는 개념.

💻 Implementation

Top-down

	public static void heapSort(int[] arr) {
		Heap h = new Heap(arr.length);
		for (int i=0;i<arr.length;i++)
			h.insert(arr[i]);
		for (int i=arr.length-1;i>=0;i--)
			arr[i] = h.deleteMax();
	}

이전에 힙을 구현했다면 간단하다. 그냥 insert하고 차례대로 삭제한 것을 담아주면 된다.

다만 Top-down으로 배열을 힙으로 바꾸는 경우인 heapification에서 시간복잡도는 O(nlogn)이 되는데, 이는 n개의 요소 모두를 힙에 넣으면서 최대 logn번의 비교가 일어나기 때문이다. heap sort의 시간 복잡도는 O(nlogn)보다 낮아질 수 없지만, heapification의 시간복잡도 감소를 위해 Bottom-up 방식을 고려해볼 수 있다.

Bottom-up

class Heap {
	private int size;
	private int idx;
	private int[] arr;

	public Heap(int n) {
		size = n;
		idx = 0;
		arr = new int[size+1];
	}

	public int[] heapSort(int[] a) {
		Heapification(a);
		while (!isEmpty())
			deleteMax();
		printAll();
		return (arr);
	}
	public int deleteMax() {
		int tmp;

		tmp = arr[1];
		arr[1] = arr[idx];
		arr[idx--] = tmp;
		heapify(1);
		return tmp;
	}

	public void heapify(int cur) {
		int maxIdx;

		if (cur*2>idx && cur*2+1>idx)
			return ;

		if (cur*2 <= idx && cur*2+1 <= idx) {
			if (arr[cur*2] > arr[cur*2+1])
				maxIdx = cur*2;
			else
				maxIdx = cur*2+1;
		}
		else
			maxIdx = cur*2;
			
		if (arr[cur] < arr[maxIdx]) {
			swap(cur, maxIdx);
			cur = maxIdx;
			heapify(cur);
		}
	}

	public boolean isEmpty() {
		return (idx == 0);
	}

	public void swap(int i, int j) {
		int tmp;

		tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}


	public void Heapification(int[] a) {
		for (int i=1;i<=a.length;i++)
			arr[i] = a[i-1];
		idx = a.length;
		int cur = (a.length+1)/2;
		while (cur > 1) {
			heapify(cur);
			cur--;
		}
	}

}

이렇게 구현하면 Heapification의 시간복잡도가 O(n)으로 좀 더 빨라진다.
증명이 약간 복잡해서 링크를 남긴다.
Heap Construction의 O(n) 증명

⌛️ Time Complexity

하지만 실제로는 Bottom-up과 top-down 상관없이 heap sort 자체는 O(nlogn)의 복잡도를 가진다. O(nlogn + nlogn) 이나 O(n + nlogn)이나 같기 때문.