Heap sort Java 코드

Heap sort

Heap에다 입력 값들을 넣은 후 루트노드를 하나씩 빼면서 정렬하는 방식

시간 복잡도

n*log2(n)

공간 복잡도

n : 힙 사이즈=입력 배열 사이즈(Heap을 수정하면 O(1)로 가능)

Java 코드

public class HeapSort {
    Heap heap; //정렬에 사용할 힙
    int[] arr; //입출력 할 배열
    
    public HeapSort(int[] _inputArr){
        heap = new Heap();
        arr = _inputArr;
    }
    
    //입력 받은 배열을 힙에 넣은 후
    //힙 루트노드를 다시 배열에 넣어서 정렬
    public int[] heapSort(){
        for(int num: arr) heap.insert(num);
        int i = 0;
        while(true){
            int num = heap.root();
            if(num == -1) break;
            arr[i++] = num;
        }        
        return arr;
    }
}