힙 정렬 - Heap Sort

2011/04/16 - [Programing/Java] - 최대 힙 최소 힙

앞에 포스팅한 최대 힙을 이용한 힙 소트 입니다.
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 + " ");
		}

	}

}