힙정렬1 [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 (.. 2021. 12. 7. 이전 1 다음