힙 정렬(Heap Sort)

이번에 배워볼 정렬 알고리즘은 힙 정렬(Heap Sort)이다.

이전에 우선순위 큐를 공부할 때 힙 자료구조에 대해서 공부하였다. 힙 자료구조는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 삽입, 삭제 연산이 O(logN)이라는 빠른 시간에 가능하기 때문에 최대, 최소 등 자신이 원하는 조건에 맞는 데이터를 정렬을 유지한 상태로 빠르게 뽑아낼 수 있는 훌륭한 자료구조였다.

힙의 특성을 활용하여 원하는 기준의 원소부터 차례대로 추출하는 방법을 힙 정렬이라 한다. 예를들어 오름차순으로 데이터를 정렬하려고 한다면 최소 힙을 구현하고 원소들을 아무렇게나 차례대로 삽입한 다음, 루트 노드(최솟값)를 데이터 개수만큼 삭제를 통해 뽑아내서 나열하면 원소들이 오름차순으로 정렬된 것을 확인할 수 있다.

 

​

힙 정렬은 1개의 데이터를 뽑아내는 시간은 루트의 데이터를 뽑아내기 때문에 O(1)이지만, 1개의 데이터를 뽑아낼 때마다 최소 힙 구조를 유지하기 위해 마지막 데이터를 루트에 삽입 후 정렬 과정에서 O(logN)의 시간이 든다.

 

힙 정렬(Heap Sort)의 시간 복잡도는 O(N logN)이다.

 

 

힙 정렬을 Java로 구현한 코드는 다음과 같다.

class MinHeap {
	int[] arr;
	int heapSize;

	public MinHeap(int n) {
		heapSize = 0;
		arr = new int[n + 1];
	}

	public void insert(int data) {
		arr[++heapSize] = data;
		int index = heapSize;

		while (index > 1 && arr[index / 2] > arr[index]) {
			int temp = arr[index / 2];
			arr[index / 2] = arr[index];
			arr[index] = temp;
			index /= 2;
		}
	}

	public int remove() {
		int ret = arr[1];
		arr[1] = arr[heapSize];
		arr[heapSize--] = 0;

		int index = 1;
		while (index * 2 <= heapSize) {
			int pos = index * 2;
			
			if (pos + 1 <= heapSize && arr[pos] > arr[pos + 1]) {
				pos += 1;
			}
			
			if (arr[index] <= arr[pos]) break;
			
			int temp = arr[pos];
			arr[pos] = arr[index];
			arr[index] = temp;
			index = pos;
		}

		return ret;
	}
}

public class Main {

	public static void main(String[] args) {
		int[] arr = {5,3,7,2,8,6,4,1};
		
		MinHeap mh = new MinHeap(arr.length);
		for (int num : arr) {
			mh.insert(num);
		}
		
		for (int i = 0; i < arr.length; ++i) {
			System.out.print(mh.remove() + " ");
		}
	}
}