855学习记录数据结构树(4)树的应用——炎泽汐$de$ Blog

文章目录[隐藏]

• 堆
• 并查集
• 哈夫曼树

定义

---

      堆应满足结构性和堆序性两个条件，首先，其逻辑结构须等同于完全二叉树，此即所谓的“结构性”。如此，堆节点将与词条一一对应。其次，就优先级而言，堆顶以外的每个节点都不大（小）于其父节点，此即所谓的“堆序性”。堆的结构等同于完全二叉树的堆，n 个词条组成的堆的高度$h = \lfloor log_2n \rfloor = O(logn)$。

基本操作

---

      此处的堆用 vector 容器实现，从索引 1 开始记录，插入算法（向上调整）的时间复杂度为$O(logn)$：

void insert(int val, vector<int>& heap){
	// val 为新增的节点值
	heap.push_back(val);
	int i = heap.size(), j = i / 2;
	while(j >= 1){
		if(heap[j] < heap[i]){
			swap(heap[j], heap[i]);
			i = j;
			j = i / 2;
		}else{
			break;
		}
	}
}

      $Floyd$建堆算法和向下调整算法为，前者时间复杂度为$O(n)$：

void DownAdjust(int low, vector<int>& heap){
	// low 为代调整节点 
	int i = low, j = i * 2;
	while(j <= heap.size()){
		if(j + 1 <= heap.size() && heap[j + 1] > heap[j]){
			j = j + 1;
		}
		if(heap[j] > heap[i]){
			swap(heap[j], heap[i]);
			i = j;
			j = i * 2;
		}else{
			break;
		}
	}
}

void CreateHeap(vector<int>& heap){
	for(int i = n / 2; i >= 1; i--){
		DownAdjust(i, heap);
	}
}

      顶节点的删除通过向下调整实现：

void DeleteTop(vector<int>& heap){
	heap[1] = heap[heap.size()];
	heap.pop_back();
	DownAdjust(1, heap);
}

定义与代码实现

---

      并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。其中“并”、“查”对应其两个关键操作。

      初始化

const int UFSetMaxn = 1000;
int father[UFSetMaxn];
void UFSetinit(int n){
	for(int i = 1; i <= n; i++){
		father[i] = i;
	}
}

      基本并查操作：

int Find(int x){
	while( x != father[x]){
		x = father[x];
	}
	return x;
}

void Union(int a, int b){
	int faA = Find(a);
	int faB = Find(b);
	if(faA != faB){
		father[faA] = faB;
	}
}

      路径压缩优化：

int FindZip(int x){
	int a = x;
	while( x != father[x]){
		x = father[x];
	}
	while(a != father[a]){
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}

void UnionZip(int a, int b){
	int faA = FindZip(a);
	int faB = FindZip(b);
	if(faA != faB){
		father[faA] = faB;
	}
}

定义与相关代码

---

//哈夫曼树 
struct HuffmanNode {
	int val;
	HuffmanNode *left;
	HuffmanNode *right;
	HuffmanNode *parent;
	HuffmanNode() : val(0), left(nullptr), right(nullptr), parent(nullptr){}
	HuffmanNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
 	HuffmanNode(int x, HuffmanNode *left, HuffmanNode *right, HuffmanNode *parent) : val(x), left(left), right(right), parent(parent) {}
}; 
//哈夫曼节点插入堆 
void insert(HuffmanNode* val, vector<HuffmanNode*>& heap){
	heap.push_back(val);
	int i = heap.size(), j = i / 2;
	while(j >= 1){
		if(heap[j] -> val > heap[i] -> val){
			swap(heap[j], heap[i]);
			i = j;
			j = i / 2;
		}else{
			break;
		}
	}
}
//哈夫曼堆向下调整 
void DownAdjust(int low, vector<HuffmanNode*>& heap){
	// low 为代调整节点 
	int i = low, j = i * 2;
	while(j <= heap.size()){
		if(j + 1 <= heap.size() && heap[j + 1] -> val > heap[j] -> val){
			j = j + 1;
		}
		if(heap[j] -> val > heap[i] -> val){
			swap(heap[j], heap[i]);
			i = j;
			j = i * 2;
		}else{
			break;
		}
	}
}
//哈夫曼堆删除顶节点 
void DeleteTop(vector<HuffmanNode*>& heap){
	heap[1] = heap[heap.size()];
	heap.pop_back();
	DownAdjust(1, heap);
}
//哈夫曼树构造合并节点 
HuffmanNode* MergeNode(HuffmanNode* a, HuffmanNode* b){
	HuffmanNode* root = new HuffmanNode(a -> val + b -> val);
	root -> left = a;
	root -> right = b;
	a -> parent = root;
	b -> parent = root;
	return root;
}
//哈夫曼树创建 
HuffmanNode* CreateHuffmanTree(vector<int>& w){
	HuffmanNode *root = new HuffmanNode();
	vector<HuffmanNode*> heap;
	heap.push_back(root);
	
	for(int i = 0; i < w.size(); i++){
		HuffmanNode *temp = new HuffmanNode(w[i]);
		insert(temp, heap);
	}
	
	for(int i = 1; i <= n - 1; i++){
		HuffmanNode* a = heap[1];
		DeleteTop(heap);
		HuffmanNode* b = heap[1];
		DeleteTop(heap);
		root = MergeNode(a, b);
		insert(root, heap);
	}
	return root;
}