앞에 포스팅한 최대 힙을 이용한 힙 소트 입니다.
1. 최대힙을 만든다.
2. 배열의 첫번째 원소를 맨뒤로 옴긴다.
3. 힙의 크기를 1 줄인다.
4. 힙의 크기가 0보다 크면 1로 돌아간다.
5. 종료
import java.util.Arrays;
public class HeapSort> {
private T[] heap;
private int size;
public static > void sort(T[] array) {
new HeapSort(array).sort();
}
private HeapSort(T[] array) {
heap = array;
size = array.length;
}
private void initialize() {
for (int i = size; i >= 0; i--) {
heapify(i);
}
}
private void sort() {
initialize();
while (size > 0) {
T temp = ExtractMax();
heap[size] = temp;
}
}
private T ExtractMax() {
T max = heap[0];
size--;
heap[0] = heap[size];
heapify(0);
return max;
}
private void heapify(int i) {
if (!hasChild(i))
return;
int k = getMaximumChild(i);
if (heap[i].compareTo(heap[k]) < 0) {
T temp = heap[i];
heap[i] = heap[k];
heap[k] = temp;
heapify(k);
}
}
private boolean hasChild(int i) {
return (i * 2 + 1) < size;
}
private int getMaximumChild(int i) {
if ((i * 2 + 2) < size) {
int max = i * 2 + 1;
if (heap[i * 2 + 1].compareTo(heap[i * 2 + 2]) < 0)
max++;
return max;
} else if (i * 2 + 1 < size) {
return i * 2 + 1;
} else {
return -1;
}
}
public static void main(String[] args) {
int size = 50;
java.util.Random rand = new java.util.Random();
Integer arr[] = new Integer[size];
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(3000);
}
Integer t[] = Arrays.copyOf(arr, arr.length);
Arrays.sort(t);
HeapSort.sort(arr);
for (Integer i : arr) {
System.out.print(i + " ");
}
System.out.println();
for (Integer i : t) {
System.out.print(i + " ");
}
}
}
