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;
}如能打赏，不胜感激[叩谢]。
标签：10,currentNode,int,heap,child,huffmanNode,数据结构,山东大学,节点 From： https://blog.csdn.net/Water_Star1/article/details/140710261