힙정렬

참고 : https://blog.naver.com/rlarjsdn529/222287695026

[Java] 힙정렬(Heap Sort) - 자바 / 그림설명 및 소스코드

import java.util.Scanner;

public class _06_03_04_힙정렬 {
	public static void main(String args[]) {
		
		// 이거슨 힙정렬, (앞에거는 병합정렬)
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		
		new _06_03_04_힙정렬().solution(n, arr);
		for (int i = 0; i < n; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public int[] solution(int n, int[] arr) {
		return heapSort(arr, n);
	}
	
	public int[] heapSort(int[] arr, int length) {
		
		if (length == 0) return arr;
		
		for (int i = 1; i < length; i++) {
			
			int child = i;
			
			while (child > 0) {
				int parent = (child - 1) / 2;
				
				if (arr[child] > arr[parent]) {
					int temp = arr[child];
					arr[child] = arr[parent];
					arr[parent] = temp;
				}
				child = parent;
			}
		}
		
		// 맨위에 가장 큰수가 있으므로 마지막과 바꿔준다
		int temp = arr[0];
		arr[0] = arr[length-1];
		arr[length-1] = temp;
		

		heapSort(arr, length-1);
		
		return arr;
	}
	
}