[アルゴリズム]ヒップ位置合わせ(Heap Sort)

お尻の位置合わせ!?

時間の複雑さ

ろんり

臀部のサイズが1より大きい場合、上記の手順を繰り返す.

ルートノードの代わりに最後のノードを使用します.(11->4)次に、最大臀部を再構成します.

private static void heapSort(int[] arr){
	int n = arr.length;
    
    for(int i=(n/2)-1; i>=0; i--{
    	heapify(arr, n, i);
    }
    
    for(int i= n-1; i>0; i--){
    	swap(arr, 0, 1);
        heapify(arr, i, 0);
    }

}

private static void heapify(int[] arr, int n, int i){
	int p = i; //부모 노드
    int l = i * 2 + 1; // 왼쪽 자식 노드
    int r = i * 2 + 2; // 오른쪽 자식 노드
    
    //왼쪽 자식 노드와 부모 노드를 비교하며 큰 값을 부모 노드로 올린다.
    if(l<n && arr[p] < arr[l]) p=l;
    
    //오른쪽 자식 노드와 부모 노드를 비교하여 큰 값을 부모 노드로 올린다.
    if(r<n && arr[p] < arr[r]) p=r;
    
    //부모 노드를 가리키는 p 값이 바뀌면 위치를 교환하고
    //heapify()를 호출하여 과정을 반복한다.
    if( i != p ){
    	swap(arr, i, p);
        heapify(arr, n, p);
    }

}

Heap Sortが利用可能な場合

Reference