HeapSort with java

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class HeapSort2 {
private static int []data;
private static int number;
 
public static void heap(int arr[], int number) {
    for(int i = 1; i < number; i++) {
        int child = i;
 
        while(child > 0) {
            int parent = (child-1)/2;
            int temp;
            if( data[child] > data[parent]) {
                temp = data[child];
                data[child] = data[parent];
                data[parent] = temp;
            }
 
            child = parent;
        }
 
    }
 
}
 
public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    try {
    int N = Integer.parseInt(br.readLine().trim());
    data = new int[N];
 
    number = N;
 
    for(int i = 0; i < data.length; i++) {
        data[i] = Integer.parseInt(br.readLine().trim());   
    }
 
    heap(data, number);
 
    for(int i = number-1; i > 0; i--) {
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
 
        heap(data, i);
 
    }
 
    for(int i = 0; i < number; i++) {
        sb.append(data[i] + "\r");
 
    }
 
    System.out.println(sb.toString());
    }catch(Exception e) {
        System.out.println(e.getMessage());
    }
}
}

 

백준 2751번 문제에 제출했는데 시간초과가 난다….
– 힙정렬은 병합정렬과 추가배열이 필요하지 않다는 점에서 메모리 측면에서 효율적
– O(N * log N)을 보장할 수 있음
– 하지만 단순히 속도만 가지고 비교하면 퀵정렬이 평균적으로 더 빠르기 때문에 힙정렬이 일반적으로 사용되진 않음(시간 복잡도는 같지만 퀵소트가 계산이 더 적음)
– O(N * log N) –> 퀵정렬, 병합정렬, 힙정렬

 

https://m.blog.naver.com/ndb796/221228342808