數據結構學習筆記＜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 通過插入操作，將 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)最小的二叉樹，其特點為：

沒有度為 1 的結點
n 個葉子結點的哈夫曼樹共有 2n-1 個結點
哈夫曼樹的任意非葉結點的左右子樹交換後仍是哈夫曼樹
同一組權值，是可能存在不同構的兩棵哈夫曼樹的

2. 哈夫曼樹的操作#

哈夫曼樹的構造，每次將權值最小的兩棵二叉樹合併
主要問題：如何選取兩個最小的？利用最小堆！

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
	int Weight;
	HuffmanTree Left,Right;
};
HuffmanTree Huffman(MinHeap H) {
	//假設H->Size個權值已經存在了H->Elements[]->Wight裡
	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;
}