データ構造学習ノート＜6＞ヒープとハフマン木と並列集合

一、ヒープ#

1. ヒープとは#

ヒープ（Heap）は、完全二分木と見なすことができる配列オブジェクトで、以下の性質を持っています：

任意のノードの値は、その部分木のすべてのノードの中で最大値 / 最小値（順序性）
ヒープは常に配列で表される完全二分木です。

2. 最大ヒープの操作関数#

定義

typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
	ElementType *Elements;//ヒープ要素を格納する配列
	int Size;//現在の要素数
	int Capacity;//最大容量
};

(1) 空の最大ヒープの作成 (Create 関数)#

MaxHeap Create(int MaxSize) {
	MaxHeap H = malloc(sizeof(struct HeapStruct) );
	H->Elements = malloc( (MaxSize+1) * sizeof(ElementType));//+1はインデックス1から格納を始めるため
	H->Size = 0;
	H->Capacity = MaxSize;
	H->Elements[0] = MaxData;//インデックス0を"哨兵"として、ヒープ内のすべての可能な要素の値より大きい値を設定し、以降の操作を容易にする
	return H;
}

(2) 最大ヒープへの挿入 (Insert 関数)#

要素を挿入する際、親ノードと比較し、挿入する要素が大きければ両者を交換し、再度親ノードと比較します。この操作を、挿入する要素が親ノードより小さくなるまで続けます。
ここに画像の説明を挿入

void Insert(MaxHeap H, ElementType item) {
	int i;
	if(IsFull(H)) {
		printf("最大ヒープは満杯です");
		return;
	}
	i = ++H->Size;//iは挿入後の最後の要素の位置を指します。
	for(; H->Elements[i/2] < item; i /= 2) {//itemの親ノードの値がitemより小さい限りループを続ける
		H->Elements[i] = H->Elements[i/2];//ノードを下にフィルタリングする（）
	}
	H->Elements[i] = item;//itemを挿入
}

(3) 最大ヒープの削除 (Delete 関数)#

根ノード（最大値）要素を取り出し、同時にヒープから根ノードを削除し、新しい根ノードが依然としてヒープ内の最大値であることを保証します。

最大ヒープの最後の要素を新しい根ノードとして使用し、元の最後の要素を削除します
根ノードの左右の子がその値より大きいかを確認し、大きければ下にフィルタリングを続けます

ElementType DeleteMax(MaxHeap H) {
	int Parent,Child;//親ノード、子ノード
	ElementType MaxItem, temp;
	if(IsEmpty(H) ) {
		printf("最大ヒープは空です");
		return;
	}
	MaxItem = H->Elements[1]; //根ノードの最大値を取り出し、MaxItemに一時保存
	temp = H->Elements[H->Size--];//最後の要素を保存し、その後size--
	for (Parent = 1; Parent*2 <= H->Size; Parent = Child) {
		Child = Parent * 2;//Childはこの時Parentの左の子
		if (Child != H->Size && H->Elements[Child] < H->Elements[Child+1] ) {
			Child++;	//右の子が存在し、かつその値が左の子より大きい場合、Childは右の子のインデックスに変わる
		} 
		if (temp >= H->Elements[Child] ) break;//tempが置くべき場所を見つけた
		else //子ノードの値で親ノードを置き換える
			H->Elements[Parent] = H->Elements[Child];
	}
	H->Elements[Parent] = temp;
	return MaxItem;//削除前の最大値を返す
}

(3) 既存の要素から最大ヒープを作成#

すでに存在する N 個の要素を最大ヒープの要件に従って 1 次元配列に格納します。

方法 1 挿入操作を通じて、N 個の要素を一つずつ空の最大ヒープに挿入し、時間計算量は最大で O (NlogN) です。
方法 2 線形時間計算量で最大ヒープを構築します。
（1）N 個の要素を入力順に格納し、完全二分木の構造特性を満たします
（2）各ノードの位置を調整し、最大ヒープの順序特性を満たします

ヒープ構築の時間計算量は O (n) で、書籍中の各ノードの高さの合計です。
最後の子ノードを持つノードから始め、そのノードは必ず左の子を持ちます。
定義中の Elements 配列を Data 配列に変更して既存の要素を格納します。

void PercDown(MaxHeap H, int p) {//H中のH->Data[p]を根とする部分ヒープを最大ヒープに調整する 原理は削除操作と同じ
	int Parent,Child;
	ElementType X;
	X = H->Data[p];//根ノードの値を取り出す
	for(Parent = p; Parent*2 <= H->Size; Parent = Child) {
		Child = Parent * 2;
		if( Child != H->Size && H->Data[Child] < H->Data[Child+1]) {
			Child++;
		}
		if(X >= H->Data[Child]) break;//適切な位置を見つけた
		else 
			H->Data[Parent] = H->Data[Child];
	}
	H->Data[Parent] = X;
}
void BuildHeap(MaxHeap H) {//H->Data[]の要素を調整し、最大ヒープの順序性を満たす。この時、すべてのH->Size個の要素がH->Data[]に存在することを仮定します
	int i;
	//最後のノードの親ノードから根ノード1まで
	for(i = H->Size/2; i > 0; i--)
		PercDown(H,i);
}

二、ハフマン木#

1. ハフマン木とは#

重み付きパス長 (WPL)：二分木にn 個の葉ノードがあり、各葉ノードに重み w~k~ が付与され、根ノードから各葉ノードまでの長さが l~k~ であるとき、各葉ノードの重み付きパス長の合計は次のようになります：WPL = $\sum_{k=1}^n$w~k~ l~k~.
最適二分木、またはハフマン木(Huffman Tree)：WPL が最小の二分木で、その特徴は：

次の度を持つノードが存在しない
n 個の葉ノードを持つハフマン木は 2n-1 個のノードを持つ
ハフマン木の任意の非葉ノードの左右の子を交換してもハフマン木である
同じ重みのセットが存在する場合、異なる構造の 2 つのハフマン木が存在する可能性がある

2. ハフマン木の操作#

ハフマン木の構築は、毎回重みが最小の 2 つの二分木を結合することです。
主な問題：どのように 2 つの最小を選択するか？最小ヒープを利用します！

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
	int Weight;
	HuffmanTree Left,Right;
};
HuffmanTree Huffman(MinHeap H) {
	//仮定としてH->Size個の重みがH->Elements[]->Weightに存在します
	int i;	HuffmanTree T;
	BuildMinHeap(H);//H->Elements[]を重みに従って最小ヒープに調整します
	for(i = 1; i < H->Size; i++) {//H->Size-1回の結合を行います
		T = malloc(sizeof(struct TreeNode));//新しいノードを作成
		T->Left = DeleteMin(H);//最小ヒープからノードを削除し、新しいTの左子ノードとします
		T->Right = DeleteMin(H);//最小ヒープからノードを削除し、新しいTの右子ノードとします
		T->Weight = T->Left->Weight + T->Right->Weight;
		Insert(H,T);//新しいTを最小ヒープに挿入
	}
	T = DeleteMin(H);
	return T;
}

3. ハフマン木の応用 —— ハフマン符号#

どのように符号化を行うと、総符号空間を最小にすることができるか？
出現頻度の高い文字には短い符号を、出現頻度の低い文字には長い符号を使用し、二義性を避ける必要があります。
接頭辞符号 (prefix code)： どの文字の符号も他の文字の接頭辞ではないため、二義性を避けることができます。
符号化のために二分木を構築することができ、左右の分岐をそれぞれ 0、1 とし、すべての文字が葉ノードにあるときに完了します。
ここに画像の説明を挿入
これでハフマン木を使用できます！

三、集合#

集合に関しては、主に並列集合についてです。以前に学んだこのブログは素晴らしいです：超有爱的并查集～(原博挂了，转载)
ですので、ここではあまり詳しくは説明しません～
ここに画像の説明を挿入

~ 並列集合の板子～#

#include <iostream>
#include <set>
using namespace std;
const int maxn = 1000000;
int fa[maxn];
int ans[maxn];
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x) {//クエリ+パス圧縮 根ノードを見つけ、経路上の各ノードの親ノードを根ノードに設定します
    return x == fa[x]? x : (fa[x] = find(fa[x]));
}
inline void merge(int a, int b) {
    fa[find(a)] = find(b);
}
int main() {
    int m, n, k, x;
    cin >> m >> n >> k;
    x = n*m;
    init(x);
    for (int i = 0; i < k; i++) {
        int a,b;
        cin >> a >> b;
        merge(a, b);
    }
    for(int i = 1; i <= x; i++) {
        ans[find(i)] = 1;
    }
    int cnt = 0;
    for (int i = 1; i <= x; i++) {
        if(ans[i] == 1) cnt++;
    }
    cout << cnt << endl;
    return 0;
}