[JAVA] 힙 정렬 (Heap Sort)

힙 정렬은 주어진 배열에 대해 힙을 구성한 후 남은 힙에서 최댓값을 순차적으로 제거하면서 정렬한다.

 

1. 주어진 배열을 힙(힙 조건을 만족시키는 완전 이진 트리)으로 만든다.
2. 다음을 (n-1)번 반복한다.
    2.1 힙에서 최댓값을 제거한다(힙의 루트 노드의 값을 마지막 노드의 값과 교환한다)
    2.2 트리에서 마지막 노드를 제거한다.
    2.3 남은 트리를 힙으로 만든다.

 

시간복잡도 O(N logN)

 

알고리즘

알고리즘 HeapSort(A[1 .. n])

eh = n
buildHeap(A, eh)

while (eh > 1) {
	A[1] <--> A[eh]
    eh = eh - 1
    pushDown(A, 1, eh/2, eh)
}

알고리즘 buildHeap(A[1 .. n], eh)

bh = (n/2) + 1
while (bh > 1) {
	bh = bh - 1
    x = bh
    pushDown(A, x, bh, eh)
}

알고리즘 pushDown(A[1 .. n], x, bh, eh)

y = findLarger(A, x, eh)
while(A[x] < A[y]) {
	A[x] <--> A[y]
    x = y
    y = findLarger(A, x, eh)
}

알고리즘 findLarger(A[1 .. n], x, eh)

if (2x + 1 <= eh) {
	if (A[2x] > A[x] || A[2x + 1] > A[x]) {
    	if (A[2x] >= A[2x + 1]) y = 2x
        else y = 2x + 1
    }
} else if (2x <= eh && A[2x] > A[x]) y = 2x
return y

 

JAVA

public class HeapSort {
	public static void main(String[] args) {
		int[] intArray = {0, 1, 2, 6, 4, 8, 7};
		int i;
		
		System.out.print("정렬 전 배열: ");
		
		for (i = 1; i < intArray.length; i++) {
			System.out.print(intArray[i] + " ");
		}
		
		heapSort(intArray);
		
		System.out.print("\n정렬 후 배열: ");
		
		for (i = 1; i < intArray.length; i++) {
			System.out.print(intArray[i] + " ");
		}
	}
	
	public static void heapSort(int[] A) {
		int eh, temp;
		
		eh = A.length - 1;
		
		buildHeap(A, eh);
		
		while (eh > 1) {
			temp = A[1];
			A[1] = A[eh];
			A[eh] = temp;
			
			eh = eh - 1;
			
			pushDown(A, 1, eh/2, eh);
		}
	}
	
	public static void buildHeap(int[] A, int eh) {
		int bh, x;
		
		bh = (A.length - 1) / 2 + 1;
		
		while (bh > 1) {
			bh = bh - 1;
			x = bh;
			
			pushDown(A, x, bh, eh);
		}
	}
	
	public static void pushDown(int[] A, int x, int bh, int eh) {
		int y, temp;
		
		y = findLarger(A, x, eh);
		
		while (A[x] < A[y]) {
			temp = A[x];
			A[x] = A[y];
			A[y] = temp;
			
			x = y;
			
			y = findLarger(A, x, eh);
		}
	}
	
	public static int findLarger(int[] A, int x, int eh) {
		int y = 0;
		
		if (2 * x + 1 <= eh) {
			if (A[2 * x] > A[x] || A[2 * x + 1] > A[x]) {
				if (A[2 * x] >= A[2 * x + 1]) y = 2 * x;
				else y = 2 * x + 1;
			}
		} else {
			if (2 * x <= eh && A[2 * x] > A[x]) y = 2 * x;
		}
		
		return y;
	}
}