A : 堆的操作

题目描述

创建 最小堆类。最小堆的存储结构使用 数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作，接下来是对堆的插入和删除操作，插入和删除都在建好的堆上操作。

输入输出格式

输入

第一行一个数 n（n<=5000)，代表堆的大小。第二行 n 个数，代表堆的各个元素。
第三行一个数 m (m<=1000)，代表接下来共 m 个操作。接下来 m 行，分别代表各个操作。下面是各个操作的格式：

• 插入操作：1 num
• 删除操作：2
• 排序操作：第一行两个数 3 和 n，3 代表是排序操作，n 代表待排序的数的数目，接下来一行 n 个数是待排序数

保证排序操作只出现一次且一定是最后一个操作。

输出

第一行建堆操作输出建好堆后堆顶的元素。
接下来 m 个操作，若是插入和删除操作，每行输出执行操作后堆顶的元素的值；若是排序操作，输出一行按升序排序好的结果，每个元素间用空格分隔。

数据结构与算法描述

创建最小堆类，私有成员有元素数组、堆中的元素个数、数组的容量。成员函数有判断数组是否为空的，还有输出根元素。

class minHeap {
private:
	int* heap;//元素数组
	int heapSize; //堆中的元素个数
	int arrayLength; //数组的容量
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new int[n+1];
		arrayLength=n+1;
	}
	~minHeap() { delete[] heap; }
	bool empty() { return heapSize == 0;}//判断heapSize是否为0.
	int Size() { return heapSize; }//返回heapSize的值
	void top() { cout << heap[1]; }//输出根 
	void pop();
	void push(int x);
	void initialize(int* theheap, int theSize);
};

插入函数先判断数组是否还有空间。如果没有将数组长度加倍。从新的叶节点开始向上遍历，直到根或者发现该位置的父节点比它小。

void minHeap::push(int x) {//插入 
	if(heapSize==arrayLength-1){//没有足够的空间 
		int* newheap=new int[arrayLength*2];//数组长度加倍 
		for(int i=1;i<=heapSize;i++){
			newheap[i]=heap[i];
		}
		delete[] heap;
		heap=newheap;
	}
	int currentNode = ++heapSize;//从新的叶节点开始 
	while (currentNode != 1 && x < heap[currentNode/2]) {//当currentNode没到根节点，并且父节点比插入的大时，继续上升 
		heap[currentNode] = heap[currentNode / 2];//将该元素的父节点下移 
		currentNode /= 2;//移向父节点 
	}
	heap[currentNode] = x;
}

删除函数将最后一个元素从根节点位置开始向下遍历，直到找到最后一个位置，或者发现两个孩子都大于本元素时。

void minHeap::pop() {//删除 
	int lastElement = heap[heapSize--];//最后一个元素 
	int currentNode = 1;//从当前被删掉的最小元素的位置开始 
	int child = 2;//currentNode的孩子 
	while (child <= heapSize) {
		if (child<heapSize && heap[child]>heap[child + 1])child++;//找到左右孩子中更小的 
		if (lastElement <= heap[child])break;//当孩子比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将较小的孩子上移 
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}

初始化函数先将原来的数组更新为新的数组，将私有成员的大小改变。然后从数组中最右一个有孩子的节点开始，依次向前遍历，判断该节点下的子树是否满足最小堆的特性，当孩子小于该节点时，需将该节点元素下移，直到小于孩子节点。

void minHeap::initialize(int* theHeap, int theSize) {//初始化
	delete[] heap;
	heap = new int[theSize + 1];
	for (int i = 1; i <= theSize; i++) {
		heap[i] = theHeap[i];
	}
	heapSize = theSize;
	for (int root = heapSize / 2; root >= 1; root--) {//从数组中最右一个有孩子的节点开始
		int rootElement = heap[root];//子树的根 
		int child = 2 * root;//rootElement的孩子位置 
		while (child <= heapSize) {
			if (child<heapSize && heap[child]>heap[child + 1])child++;//找到孩子里较小的 
			if (rootElement <= heap[child])break;//如果子树的根小于其孩子，则可以跳出循环 
			//如果孩子较小
			heap[child / 2] = heap[child];//将孩子上移 
			child *= 2;
		}
		heap[child / 2] = rootElement;
	}
}

排序操作，将新的数组初始化为最小堆后，依次输出堆顶元素（即最小元素）然后调用删除函数，直到堆为空。

完整代码（含注释）

#include<iostream>
using namespace std;
class minHeap {
private:
	int* heap;//元素数组
	int heapSize; //堆中的元素个数
	int arrayLength; //数组的容量
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new int[n+1];
		arrayLength=n+1;
	}
	~minHeap() { delete[] heap; }
	bool empty() { return heapSize == 0;}//判断heapSize是否为0.
	int Size() { return heapSize; }//返回heapSize的值
	void top() { cout << heap[1]; }//输出根 
	void pop();
	void push(int x);
	void initialize(int* theheap, int theSize);
};
void minHeap::push(int x) {//插入 
	if(heapSize==arrayLength-1){//没有足够的空间 
		int* newheap=new int[arrayLength*2];//数组长度加倍 
		for(int i=1;i<=heapSize;i++){
			newheap[i]=heap[i];
		}
		delete[] heap;
		heap=newheap;
	}
	int currentNode = ++heapSize;//从新的叶节点开始 
	while (currentNode != 1 && x < heap[currentNode/2]) {//当currentNode没到根节点，并且父节点比插入的大时，继续上升 
		heap[currentNode] = heap[currentNode / 2];//将该元素的父节点下移 
		currentNode /= 2;//移向父节点 
	}
	heap[currentNode] = x;
}
void minHeap::pop() {//删除 
	int lastElement = heap[heapSize--];//最后一个元素 
	int currentNode = 1;//从当前被删掉的最小元素的位置开始 
	int child = 2;//currentNode的孩子 
	while (child <= heapSize) {
		if (child<heapSize && heap[child]>heap[child + 1])child++;//找到左右孩子中更小的 
		if (lastElement <= heap[child])break;//当孩子比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将较小的孩子上移 
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}
void minHeap::initialize(int* theHeap, int theSize) {//初始化
	delete[] heap;
	heap = new int[theSize + 1];
	for (int i = 1; i <= theSize; i++) {
		heap[i] = theHeap[i];
	}
	heapSize = theSize;
	for (int root = heapSize / 2; root >= 1; root--) {//从数组中最右一个有孩子的节点开始
		int rootElement = heap[root];//子树的根 
		int child = 2 * root;//rootElement的孩子位置 
		while (child <= heapSize) {
			if (child<heapSize && heap[child]>heap[child + 1])child++;//找到孩子里较小的 
			if (rootElement <= heap[child])break;//如果子树的根小于其孩子，则可以跳出循环 
			//如果孩子较小
			heap[child / 2] = heap[child];//将孩子上移 
			child *= 2;
		}
		heap[child / 2] = rootElement;
	}
}
int main() {
	int n;//堆大小 
	cin >> n;
	int a[n+1];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	minHeap mh(n);
	mh.initialize(a, n);//将堆初始化 
	mh.top();
	cout << endl;
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		if (x == 1) {
			int num;
			cin >> num;
			mh.push(num);
			mh.top();
			cout << endl;
		}
		else if (x == 2) {
			mh.pop();
			mh.top();
			cout << endl;
		}
		else if (x == 3) {
			int n2;
			cin >> n2;
			minHeap mh2(n2);
			int b[n2+1];
			for (int j = 1; j <= n2; j++) {
				cin >> b[j];
			}
			mh2.initialize(b, n2);
			while(!mh2.empty()) {//依次输出最小元素，并删除 
				mh2.top();
				cout << " ";
				mh2.pop();
			}
		}
	}
	return 0;
}

B : 霍夫曼编码

输入输出格式

输入

一串小写字母组成的字符串（不超过 1000000)。

输出

输出这个字符串通过 Huffman 编码后的长度。

数据结构与算法描述

在主函数中创建一个26大小的数组，用于判断字符串中所包含姊妹种类个数以及各个字母的频数。将频数不为0的字母的频数，传到到一个新的数组，以备构造霍夫曼树用。

	string str;
	cin>>str;
	int *num=new int[26];
	int numzm=0;//字母种类个数 
	for(int i=0;i<26;i++)num[i]=0;//将26个字母的个数初始化为0 
	for(int i=0;i<str.size();i++){
		num[(int)str[i]-(int)'a']++;//对应的位置加一 
		if(num[(int)str[i]-(int)'a']==1){//当该字母有一个 
			numzm++;//种类数加一 
		}
	}

还需要一个队列类，一个霍夫曼树结点的结构体，其成员包括几点的权值、结点到根的高度、左右孩子。还要有一个最小堆，存储结构用链表，大小比较以节点的权值为准。

template<class T>
class queue {
private:
	int queuefront;//第一个数前一个位置的索引
	int queueback;//最后一个数的索引
	int arraylength;//队列长度
	T* queue0;
public:
	queue(int l) {
		arraylength = l;
		queue0 = new T[arraylength];
		queuefront = queueback = 0;
	}
	~queue() { delete[] queue0; }
	bool empty()const { return queuefront==queueback; }//是否为空
	int qsize()const { return queueback - queuefront; }//列表大小
	T& front() { return queue0[queuefront]; }//第一个位置
	void pop() {//删除
		queuefront++;
	}
	void push(T& theelement) {//插入
		queue0[queueback] = theelement;
		queueback++; 
	}
};
struct huffmanNode{//霍夫曼树节点 
	int weight;//权值
	int height;//节点到根的高度
	huffmanNode* leftchild; 
	huffmanNode* rightchild;
};
class minHeap {//最小堆 
private:
	huffmanNode** heap;//节点指针数组
	int heapSize; //堆中的元素个数
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new huffmanNode*[n+1];
	}
	~minHeap() { delete[] heap; }
	huffmanNode* top() { return heap[1]; }//返回根 
	void pop();
	void push(huffmanNode* x);
	void initialize(huffmanNode** theheap, int theSize);
};
void minHeap::push(huffmanNode* x) {//插入 
	int currentNode = ++heapSize;//从新的叶节点开始 
	//当currentNode没到根节点，并且父节点权值比插入的大时，继续上升
	while (currentNode != 1 && x->weight < heap[currentNode/2]->weight) {
		heap[currentNode] = heap[currentNode / 2];//将该元素的父节点下移 
		currentNode /= 2;//移向父节点 
	}
	heap[currentNode] = x;
}
void minHeap::pop() {//删除 
	huffmanNode* lastElement = heap[heapSize--];//最后一个节点
	int currentNode = 1;从当前被删掉的最小权值的位置开始 
	int child = 2;//currentNode的孩子
	while (child <= heapSize) {
		if (child<heapSize && heap[child]->weight>heap[child + 1]->weight)child++;//找到左右孩子权值中更小的 
		if (lastElement->weight <= heap[child]->weight)break;//当孩子的权值比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将权值较小的孩子上移
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}
void minHeap::initialize(huffmanNode** theHeap, int theSize) {//初始化
	for (int i = 1; i <= theSize; i++) {
		heap[i] = theHeap[i-1];
	}
	heapSize = theSize;
	for (int root = heapSize / 2; root >= 1; root--) {//从链表中最右一个有孩子的节点开始
		huffmanNode* rootElement = heap[root];//子树的根 
		int child = 2 * root;//rootElement位置的孩子的位置 
		while (child <= heapSize) {
			if (child<heapSize && heap[child]->weight>heap[child + 1]->weight)child++;//找到孩子里权值较小的 
			if (rootElement->weight <= heap[child]->weight)break;//如果子树的根的权值小于其孩子，则可以跳出循环 
			//如果孩子权值较小
			heap[child / 2] = heap[child];//将孩子上移 
			child *= 2;
		}
		heap[child / 2] = rootElement;
	}
}

霍夫曼树类私有成员有树的节点数、根节点。公有成员构造霍夫曼树函数，先声明一个节点的指针数组，并将主函数的新数组中各个字母的权值，依次传给指针数组。然后将指针数组传给最小堆的初始化函数进行排序。然后通过循环，依次从堆中弹出权值最小的节点，将两个节点构成一个新节点的左右孩子，新节点的权值为两个孩子权值之和。直到构成一个树。堆最后一个形成的新节点，就是霍夫曼树的根。计算编码长度的函数，类似二叉树的层次遍历，利用队列的先进先出，从根节点还是插入队列中，在循环中依次检查队首节点是否有孩子，孩子节点到根的高度，为其父节点到根的高度加一。当一个节点没有左右孩子时，就是外部节点，总长度就要加上高度（编码长度）与权值（频率）的积

class huffmanTree{//霍夫曼树 
	private:
		int num;//树的节点数 
		huffmanNode* root;//根节点 
	public:
		void maketree(int *a,int n){//构造霍夫曼树 
			huffmanNode** heap=new huffmanNode* [n];//节点的指针数组 
			for(int i=0;i<n;i++){//将权值依次传给指针数组 
				heap[i]=new huffmanNode();
				heap[i]->weight=a[i];
				heap[i]->leftchild=heap[i]->rightchild=NULL;
			}
			minHeap mh(n);
			mh.initialize(heap,n);//利用最小堆将节点升序排序 
			huffmanNode *z,*l,*r;
			for(int i=1;i<n;i++){
				//找到两个权值最小的节点 
				l=mh.top();
				mh.pop();
				r=mh.top();
				mh.pop();
				z=new huffmanNode;
				//将两个权值最小的节点作为新节点的左右节点 
				z->leftchild=l;
				z->rightchild=r;
				z->weight=l->weight+r->weight;//新节点的权值位两个子树的权值之和 
				mh.push(z);//将新节点插入最小堆中 
			}
			num=n;
			root=mh.top();//根为最后形成的新节点 
			mh.pop();
		}
		void length(){//编码长度 
			int h=0;//初始化长度为0 
			queue<huffmanNode*>q(num*2-1);//利用队列先入先出 
			huffmanNode* b;
			q.push(root);//将根插入队列 
			root->height=0;
			while(!q.empty()){//类似层次遍历 
				b=q.front();
				q.pop();
				if(b->leftchild!=NULL){ 
					q.push(b->leftchild);
					b->leftchild->height=b->height+1;//节点到根的高度，为其父节点到根的高度加一 
				}
				if(b->rightchild!=NULL){
					q.push(b->rightchild);
					b->rightchild->height=b->height+1;
				}
				if(b->leftchild==NULL&&b->rightchild==NULL){//没有子节点说明到了外部节点 
					h+=b->height*b->weight;//总长度加上了高度（编码长度）与权值（频率）的积 
				}
			}
			cout<<h<<endl;
		}
};

完整代码（含注释）

#include<iostream>
#include<string> 
using namespace std;
template<class T>
class queue {
private:
	int queuefront;//第一个数前一个位置的索引
	int queueback;//最后一个数的索引
	int arraylength;//队列长度
	T* queue0;
public:
	queue(int l) {
		arraylength = l;
		queue0 = new T[arraylength];
		queuefront = queueback = 0;
	}
	~queue() { delete[] queue0; }
	bool empty()const { return queuefront==queueback; }//是否为空
	int qsize()const { return queueback - queuefront; }//列表大小
	T& front() { return queue0[queuefront]; }//第一个位置
	void pop() {//删除
		queuefront++;
	}
	void push(T& theelement) {//插入
		queue0[queueback] = theelement;
		queueback++; 
	}
};
struct huffmanNode{//霍夫曼树节点 
	int weight;//权值
	int height;//节点到根的高度
	huffmanNode* leftchild; 
	huffmanNode* rightchild;
};
class minHeap {//最小堆 
private:
	huffmanNode** heap;//节点指针数组
	int heapSize; //堆中的元素个数
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new huffmanNode*[n+1];
	}
	~minHeap() { delete[] heap; }
	huffmanNode* top() { return heap[1]; }//返回根 
	void pop();
	void push(huffmanNode* x);
	void initialize(huffmanNode** theheap, int theSize);
};
void minHeap::push(huffmanNode* x) {//插入 
	int currentNode = ++heapSize;//从新的叶节点开始 
	//当currentNode没到根节点，并且父节点权值比插入的大时，继续上升
	while (currentNode != 1 && x->weight < heap[currentNode/2]->weight) {
		heap[currentNode] = heap[currentNode / 2];//将该元素的父节点下移 
		currentNode /= 2;//移向父节点 
	}
	heap[currentNode] = x;
}
void minHeap::pop() {//删除 
	huffmanNode* lastElement = heap[heapSize--];//最后一个节点
	int currentNode = 1;从当前被删掉的最小权值的位置开始 
	int child = 2;//currentNode的孩子
	while (child <= heapSize) {
		if (child<heapSize && heap[child]->weight>heap[child + 1]->weight)child++;//找到左右孩子权值中更小的 
		if (lastElement->weight <= heap[child]->weight)break;//当孩子的权值比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将权值较小的孩子上移
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}
void minHeap::initialize(huffmanNode** theHeap, int theSize) {//初始化
	for (int i = 1; i <= theSize; i++) {
		heap[i] = theHeap[i-1];
	}
	heapSize = theSize;
	for (int root = heapSize / 2; root >= 1; root--) {//从链表中最右一个有孩子的节点开始
		huffmanNode* rootElement = heap[root];//子树的根 
		int child = 2 * root;//rootElement位置的孩子的位置 
		while (child <= heapSize) {
			if (child<heapSize && heap[child]->weight>heap[child + 1]->weight)child++;//找到孩子里权值较小的 
			if (rootElement->weight <= heap[child]->weight)break;//如果子树的根的权值小于其孩子，则可以跳出循环 
			//如果孩子权值较小
			heap[child / 2] = heap[child];//将孩子上移 
			child *= 2;
		}
		heap[child / 2] = rootElement;
	}
}
class huffmanTree{//霍夫曼树 
	private:
		int num;//树的节点数 
		huffmanNode* root;//根节点 
	public:
		void maketree(int *a,int n){//构造霍夫曼树 
			huffmanNode** heap=new huffmanNode* [n];//节点的指针数组 
			for(int i=0;i<n;i++){//将权值依次传给指针数组 
				heap[i]=new huffmanNode();
				heap[i]->weight=a[i];
				heap[i]->leftchild=heap[i]->rightchild=NULL;
			}
			minHeap mh(n);
			mh.initialize(heap,n);//利用最小堆将节点升序排序 
			huffmanNode *z,*l,*r;
			for(int i=1;i<n;i++){
				//找到两个权值最小的节点 
				l=mh.top();
				mh.pop();
				r=mh.top();
				mh.pop();
				z=new huffmanNode;
				//将两个权值最小的节点作为新节点的左右节点 
				z->leftchild=l;
				z->rightchild=r;
				z->weight=l->weight+r->weight;//新节点的权值位两个子树的权值之和 
				mh.push(z);//将新节点插入最小堆中 
			}
			num=n;
			root=mh.top();//根为最后形成的新节点 
			mh.pop();
		}
		void length(){//编码长度 
			int h=0;//初始化长度为0 
			queue<huffmanNode*>q(num*2-1);//利用队列先入先出 
			huffmanNode* b;
			q.push(root);//将根插入队列 
			root->height=0;
			while(!q.empty()){//类似层次遍历 
				b=q.front();
				q.pop();
				if(b->leftchild!=NULL){ 
					q.push(b->leftchild);
					b->leftchild->height=b->height+1;//节点到根的高度，为其父节点到根的高度加一 
				}
				if(b->rightchild!=NULL){
					q.push(b->rightchild);
					b->rightchild->height=b->height+1;
				}
				if(b->leftchild==NULL&&b->rightchild==NULL){//没有子节点说明到了外部节点 
					h+=b->height*b->weight;//总长度加上了高度（编码长度）与权值（频率）的积 
				}
			}
			cout<<h<<endl;
		}
};
int main(){
	string str;
	cin>>str;
	int *num=new int[26];
	int numzm=0;//字母种类个数 
	for(int i=0;i<26;i++)num[i]=0;//将26个字母的个数初始化为0 
	for(int i=0;i<str.size();i++){
		num[(int)str[i]-(int)'a']++;//对应的位置加一 
		if(num[(int)str[i]-(int)'a']==1){//当该字母有一个 
			numzm++;//种类数加一 
		}
	}
	int *b=new int[numzm];//b数组统计各个字母的频数（权值） 
	int d=0;
	for(int i=0;i<26;i++){
		if(num[i]!=0){
			b[d]=num[i];
			d++;
		}
	}
	huffmanTree ht;
	ht.maketree(b,numzm);
	ht.length();
	return 0;
}

如能打赏，不胜感激[叩谢]。