힙 정렬( Heap sort ) 알고리즘

힙 정렬 알고리즘?

최대 힙 이나 최소 힙을 구성해 정렬하는 방법

내림차순은 최대 힙, 오름차순은 최소 힙  

 

힙?

https://chjysm.tistory.com/33

힙(heap)

 

정렬 절차

1. 정렬해야 할 n개의 요소들로 힙 을 만든다.
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열에 저장한다.
   
   

특징

장점

• 성능이 좋은편이다.
• 전체 자료를 정렬하는 기능 보다는 가장 큰 값과 작은 값이 필요한 경우이다.

 

구현

public static void heapSort( int[] target ){

    // 최소힙 생성
    Heap heap = new Heap( target.length, false );
    for( int i : target ){
        heap.add(i);
    }

    for( int i = 0; i < target.length; i++){
        target[i] = heap.delete();
    }
}

 

시간 복잡도

최상, 평균, 최악 : nlogn

 

---

참조

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog