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

お尻の位置合わせ!?

完全バイナリツリーの遅いデータ構造に基づくソート方法.

不安定ソート

完全バイナリツリー

を挿入すると、左から順にバイナリツリー

が追加される.

時間の複雑さ

平均値:O(Nlogn)

最適:O(Nlogn)

最悪:O(Nlogn)

ろんり

の最大臀部を構成する.

現在、ヒップホップには最大の値が存在します.ルートの値を最後の要素と交換した後、ヒップのサイズを小さくします.

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

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

Heap Sortはこのようにして最大値を1つずつ抽出してソートする.

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);
    }

}

最初のheapify

は一般的に臀部で構成される役割を果たしている.

親ノードを

子ノードから比較します.

(n/2)-なぜ1から0に移動したのですか?
:親ノードのインデックスに基づいて、左側のサブノード:ix 2+1、右側のサブノード:ix 2+2.

2番目heapify

要素が削除された後に最大臀部を再構成するために使用されます.

コースを基準に行います.

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);
    }

}

は、最大hipが再構成され、再帰が呼び出されるまで、親ノードと子ノードを交換する.

の高速ソートとマージソートの性能は良好であるため、hipソートの使用頻度は高くない.

ですが、hip資料構造が多く使われており、それに伴う概念はheap sortです.

Heap Sortが利用可能な場合

最大または最小値を求める場合:最小ヒップ、最大ヒップの根値は、一度のヒップ配置で求めることができる.

の最大kの要素を決定する場合:ソートを挿入するよりも、より良い効果が得られます.

参考までにPriorityQueueはお尻で構成されています.😎

Reference

Ready-For-Tech-Interview