최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨
성능
시간복잡도 최악의 경우 : n log2(n) 최선의 경우 : n log2(n) : 데이터 저장 및 삭제의 시간복잡도 log2(n) : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n
데이터 저장 및 삭제의 시간복잡도 - 트리의 높이가 하나씩 증가할 때마다 데이터의 수는 증가 전 높이의 데이터 수보다 최대 2배 증가한다.
그러나 데이터를 추가 및 삭제할 때는 부모노드와 같을 비교하기 때문에 데이터의 수는 2배 증가하지만 비교횟수는 1회 증가되는 것으로 이를 일반화하면 대략적으로 비교횟수 = log2(데이터 개수)이 된다.
구현
기본 구현 [HeapBasic.java]
package Sort.Heap;
import java.util.Collections;
import java.util.PriorityQueue;
public class HeapBasic {
public static void sort(int[] arr, boolean isDescending) {
PriorityQueue<Integer> pq = null;
pq = init(isDescending);
add(pq, arr);
for(int i=0; i<arr.length; i++) {
arr[i] = pq.remove();
}
}
private static PriorityQueue init(boolean isDescending) {
PriorityQueue pq = null;
// 내림차순일 경우 최대힙으로 구성
if (isDescending) {
pq = new PriorityQueue<>(Collections.reverseOrder());
}
// 오름차순일 경우 최소힙으로 구성
else {
pq = new PriorityQueue<>();
}
return pq;
}
private static void add(PriorityQueue pq, int[] arr) {
for(int i=0; i<arr.length; i++) {
pq.add(arr[i]);
}
}
private static int delete(PriorityQueue pq) {
return (int)pq.remove();
}
}
테스트 [HeapBasicMain.java]
package Sort.Heap;
public class HeapBasicMain {
private static final int MAX_COUNT = 10;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (오름차순)");
int[] ascHeapSortTestArray = arr.clone();
HeapBasic.sort(ascHeapSortTestArray, false);
for(int i : ascHeapSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (내림차순)");
int[] descHeapSortTestArray = arr.clone();
HeapBasic.sort(descHeapSortTestArray, true);
for(int i : descHeapSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
