include

include

include

include

include

include

using namespace std;
int main() {
string s;
priority_queue<int, vector<int>, greater<int> > Q;
puts("ACSII coding and Huffman coding efficiency comparison\n");
while (printf("Input string:\n"), getline(cin, s) && s != "END") {
sort(s.begin(), s.end());
int t = 1;
for (int i = 1; i < s.length(); ++i)
if (s[i] != s[i - 1])
Q.push(t), t = 1;
else
++t;
Q.push(t);
int ans = 0, a, b;
if (Q.size() == 1) ans = Q.top();
while (Q.size() > 1) {
a = Q.top(), Q.pop();
b = Q.top(), Q.pop();
Q.push(a + b);
ans += a + b;
}
Q.pop();
printf(
"\nASCII Coding\t\t%lu byte\nHuffman Coding\t\t%d byte\nCompression ratio\t%.2f\n\n",
s.size() * 8, ans, (s.size() * 8.0) / ans);
}
return 0;</int></int>

}#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
class HuffmanTree {
struct node {
int weight;
struct node *Lchild, *Rchild;
bool operator<(const node &x) const { return weight < x.weight; }
bool operator>(const node &x) const { return weight > x.weight; }
};</vector></string></queue></iostream></cstdio></algorithm>

typedef priority_queue<node, vector<node>, greater<node> > HuffQueue;

HuffQueue GetWeight() {
    cout << "Input nodes' power, end with -1" << endl;
    HuffQueue q;
    int temp;
    while (cin >> temp, temp != -1) q.push({temp, NULL, NULL});
    return q;
}

node *CreatHuffmanTree(HuffQueue q) {
    node *root = new node;
    if (q.size() == 1) {
        *root = q.top();
        return root;
    }
    while (q.size() > 1) {
        node *Lch = new node, *Rch = new node, *P = new node;
        *Lch = q.top(), q.pop();
        *Rch = q.top(), q.pop();
        P->Lchild = Lch, P->Rchild = Rch,
        P->weight = Lch->weight + Rch->weight;
        q.push(*P);
    }
    *root = q.top();
    return root;
}

void PreOrderVisit(node *root) {
    if (root == NULL) return;
    if (root->Lchild == NULL && root->Rchild == NULL) printf("LeafNode");
    printf("%d\n", root->weight);
    PreOrderVisit(root->Lchild);
    PreOrderVisit(root->Rchild);
}

void DestoryHuffmanTree(node *root) {
    if (root == NULL) return;
    DestoryHuffmanTree(root->Lchild);
    DestoryHuffmanTree(root->Rchild);
    delete root;
}

public:
void show() {
HuffQueue q = GetWeight();
node *root = CreatHuffmanTree(q);
PreOrderVisit(root);
DestoryHuffmanTree(root);
}
};