ヒップ位置合わせ(Heap Sort)

定義＃テイギ＃

HIP:最小値または最大値をすばやく検索するために完全なツリー形式で作成されたデータ構造
ノードは常に優先度の高いノード==最大値と最小値をすばやく見つけることができます.(時間複雑度:O(1))

最小HIP:各ノードの値はそのサブノードの値

より小さい.

最大HIP:各ノードの値がそのサブノードの値

より大きい
-お尻の構造は反対整列状態で、完全整列状態ではありません!hip構造+ソートプロセス

ソート方法

初期状態=>最大ヒップホップ=>ソート

最大heapify

-初期状態の配列を最大スタックとして作成する必要があります.配列を宣言する必要はありません.追加のメモリ領域を作成することなく、元の配列でソートできます.
-一番小さいサブツリーから、一番大きいお尻を満たすように順番に実行します.
-このステータスはソートされていません!HIPは、最大値または最小値をすばやく検索するためのデータ構造です.

ソート

-ルートノードには常に最大値があります.最大値を削除し、配列の最後から塗りつぶします.
(ルート要素をアレイの後ろに送信->残りのアレイ要素を最大ヒップホップ要件を満たすように再構成しますが、後ろに埋め込まれた要素を除きます)

コード#コード#

再帰(Top-Down形式)

public static void sort(int[] a) {
	sort(a,a.length);
}
private static void sort(int[] a, int size) {
	//원소가 1개이거나 0개일 경우 정렬할 필요가 없으므로 함수를 종료
	if (size < 2) return;
    
    //가장 마지막 요소의 부모 인덱스
    int parentIdx = getParent(size - 1);
    
    //최대힙 구성
    for(int i = parentIdx; i >= 0; i--) {
    	heapify(a, i, size - 1);
    }
    
    //root인 0번째인덱스와 i번째 인덱스의 값을 교환해준 뒤
    //0 ~ (i - 1)까지의 부분트리에 대해 max heap을 만족하도록 재구성
    for (int i = size - 1; i > 0; i--) {
    	swap(a, 0, i);
        heapify(a, 0, i - 1);
        //heapify하면 index : 0값에는 (0~i-1)값의 최대값이 있음
    }
}

//부모 인덱스를 얻는 함수
private static int getParent(int child) {
	return (child - 1) / 2;
}

//두 인덱스의 원소를 교환하는 함수
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

//힙을 재구성하는 함수
private static void heapify(int[] a, int parentIdx, int lastIdx) {
	
    //현재 트리에서 부모 노드의 자식노드 인덱스를 각각 구해준다.
    //현재 부모 인덱스를 가장 큰 값을 갖고있다고 가정한다.
    
    int leftChildIdx = 2 * parentIdx + 1;
    int rightChildIdx = 2 * parentIdx + 2;
    int largestIdx = parentIdx;
    
    //자식노드 인덱스가 트리의 크기를 넘어가지 않으면서, 현재 가장 큰 인덱스보다 왼쪽 자식노드의 값이 더 클경우, 가장 큰 인덱스를 가리키는 largestIdx를 왼쪽 자식노드 인덱스로 바꿔준다.
   	if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
    	largestIdx = leftChildIdx;
    }
    //자식 노드 인덱스가 트리의 크기를 넘어가지 않으면서, 현재 가장 큰 인덱스보다 오른쪽쪽 자식노드의 값이 더 클경우, 가장 큰 인덱스를 가리키는 largestIdx를 오른쪽 자식 노드인덱스로 바꿔준다.
    if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
    largestIdx = rightChildIdx;
	}
    
    //largestIdx와 부모노드가 같지 않다는 것은
    //위 자식 노드 비교 과정에서 현재 부모노드보다 큰 노드가 존재한다는 뜻이다.
    //그럴 경우 해당 자식 노드와 부모노드를 교환해주고,
    //교환된 자식 노드를 부모노드로 삼은 서브트리를 검사하도록 재귀 호출한다.
    if(parentIdx != largestIdx) {
    	swap(a, largestIdx, parentIdx);
        heapify(a, largestIdx, lastIdx);
    }
}   

長所と短所

-メリット

最悪の場合もO(Nlogn)のまま

部分並べ替え時の効果は良好

-欠点
性能は

の従来のO(Nlogn)ソートアルゴリズムと比較して

低下した.

は一度に最大お尻を作り、不安定なソート状態では最大値だけを取ってソートするので、安定したソートではありません.

時間の複雑さ

heapify:ツリーの深さで比較交換=O(logn)
アレイを最も大規模にする過程はO(N)の時間的複雑さである.
お尻の要素を一番後ろに送り、残りの要素のお尻を再編成します:N個の要素*log(N)=O(NlogN)