哈夫曼树

前置c语言知识

结构体指针

// typedef struct Student*  Stu；
//这里相当于给结构体指针变量起名为Stu，注意在这里Stu为一个类型，而不是变量，Stu st1，st2要访问结构体中的数据时st1->成员变量；
//结构体类型定义： 
struct Student{
	      char number;
	      char name;
	      bool sex;
	      struct Student *Next；//结构体支持自定义
};
typedef struct Student *Stu；
（也可以放在结构体前，但这种写法不太规范）
Stu st1；//st1定义为struct Student 类型的指针变量

上面的例子等价于：
typedef struct Student{
          char number;
	      char name;
	      bool sex;
	      struct Student *Next；
}*Stu；
Stu st1;//这个语句定义了一个名为st1的结构体指针

优先队列

实现霍夫曼树需要用堆的功能，但是我们不重复写轮子，这里我们直接使用STL优先队列实现。要注意优先队列/堆里面存储的是结构体指针node *，而不是结构体节点node。否则无法建树，所以使用结构体方法重载小于号。(第三种)
四种重载优先级的方法。霍夫曼树实现的难点就在这里。

结构体内部重载小于号

priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号

使用标准库函数写法


priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起，“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;

结构体外自定义重载方法，注意此处是结构体而非函数

//优先队列的重载大小方法是一个结构体
struct cmp
{
	bool operator () (const node &x,const node &y) const
	{
		return //需要的真值情况;
	}
};

priority_queue<node,vector<node>,cmp> q;

使用decltype关键字进行重载

这个是从网上看到的不太明白原理。

auto f = [](Tnode* t1, Tnode* t2) {return t1->weight > t2->weight; };
priority_queue<Tnode*, vector<Tnode*>, decltype(f)>heap(f);

优先队列练习

美团笔试题
餐厅n个桌子，男喜欢坐一个人，女喜欢坐没有人，除非没符合条件的。
给出男女进入顺序，安排编号最小座位。

#include<bits/stdc++.h>
#include<queue>
#include<bits/stdc++.h>

using namespace std;

priority_queue<int,vector<int>, greater<int>  >number_0,number_1,init;
const int N=5e5+10;
char s[N],sex[2*N];//1e7级别的输出千万别用cin，关闭cin流动也过不了 

void add_0(){
	int k=number_0.top();
	number_0.pop();
	number_1.push(k);
	printf("%d\n",k);
}

void add_1(){
	printf("%d\n",number_1.top());
	number_1.pop();	
}


int main(){
	int t,n,len;
	scanf("%d",&t);
	while(t--){
		number_0=init;
		number_1=init;
		//cin>>n>>s;
		scanf("%d",&n);
		scanf("%s",s);
		for(int i=0;i<n;i++){
			if(s[i]=='0') number_0.push(i+1);
			if(s[i]=='1') number_1.push(i+1);
		}
		
		
		scanf("%d",&len);
		scanf("%s",sex);
		for(int i=0;i<len;i++){
			if(sex[i]=='M'){
				if(!number_1.empty())add_1();
				else add_0();
			}
			if(sex[i]=='F'){
				if(!number_0.empty())add_0();
				else add_1();
			}			
		}	
	}
	
}

哈夫曼树建树

知乎代码模板
 例题练习

这个模板同样可以用于求前缀编码

#include<bits/stdc++.h>

using namespace std;

struct Tnode
{
	int weight;
	Tnode* left, * right;
	Tnode(int x) :weight(x), left(nullptr), right(nullptr) {};
};

struct cmp{
	bool operator()( Tnode* x, Tnode* y)  {
		return x->weight > y->weight;//值小优先 
	}
};

pair<Tnode*, int> Huffman(const vector<int>& v)
{
	//auto f = [](Tnode* t1, Tnode* t2) {return t1->weight > t2->weight; };
	//priority_queue<Tnode*, vector<Tnode*>, decltype(f)>heap(f);
	priority_queue<Tnode*, vector<Tnode*>, cmp>heap;
	for (auto& x : v) heap.push(new Tnode(x));
	//Tnode* p=new Tnode(x) 使用结构体指针指像实例化节点
	int sum = 0;
	while (heap.size() > 1)
	{
		auto t1 = heap.top(); heap.pop();
		auto t2 = heap.top(); heap.pop();
		auto r = new Tnode(t1->weight + t2->weight);
		r->left = t1; r->right = t2;
		sum+= (t1->weight + t2->weight);
		heap.push(r);
	}
	return { heap.top(),sum };
}

int dfs(Tnode* root, int pathlen)                         //根据Huffman树根节点求出带权路径长度之和
{
	if (!root->left && !root->right) return pathlen * root->weight;
	return dfs(root->left, pathlen + 1) + dfs(root->right, pathlen + 1);
}

int main(){
	int n;
	cin>>n;
	vector<int >a;
	while(n--){
		int val;
		cin>>val;
		a.push_back(val);
	}
	cout<<Huffman(a).second<<endl;
}