[JAVA] 힙 정렬 (Heap Sort)

[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("

정렬 후 배열: "); 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; } }

from http://pekahblog.tistory.com/182 by ccl(S) rewrite - 2021-12-07 15:26:28