【Openjudg】Huffmanコードツリー
2842 ワード
自分でひと山作った
#include
#include
using namespace std;
template
class Heap{
T* root;
int current_size, max_size;
public:
Heap():root(0), current_size(0), max_size(0){};
int parent(int cur) const{
return (cur - 1) / 2;
}
int left_child(int cur) const{
return 2 * cur + 1;
}
int right_child(int cur) const{
return 2 * cur + 1;
}
void shift_down(int pos){
int i = pos;
int j = left_child(pos);
T temp = root[pos];
while(j < current_size){
if (j + 1 < current_size && root[j + 1] < root[j]){
j ++;
}
if (root[j] < temp){
root[i] = root[j];
i = j;
j = 2 * j + 1;
}
else{
break;
}
}
root[i] = temp;
}
void shift_up(int pos){
T temp = root[pos];
int i = pos;
while (i > 0 && temp < root[parent(i)]){
root[i] = root[parent(i)];
i = parent(i);
}
root[i] = temp;
}
void build(const T* array, int amount){
root = new T[amount];
current_size = max_size = amount;
memcpy(root, array, sizeof(T) * amount);
for (int i = current_size / 2 - 1; i >= 0; i --){
shift_down(i);
}
}
T heapmin(){
return root[0];
}
bool dlt(int pos){
if (pos < 0 || pos >= current_size){
return false;
}
T t = root[pos];
root[pos] = root[--current_size];
shift_up(pos);
shift_down(pos);
return true;
}
bool insert(const T& t){
if (current_size == max_size){
return false;
}
root[current_size] = t;
shift_up(current_size);
current_size ++;
return true;
}
};
struct _node{
int data;
_node* left;
_node* right;
_node(int d = 0):data(d), left(NULL), right(NULL){};
bool isLeaf(){
return (left == NULL && right == NULL);
}
bool operatordata << endl;
if(root->isLeaf()){
sum += depth * root->data;
// cout << sum << endl;
depth --;
return;
}
if (root->left){
depth ++;
travel_and_sum(root->left, sum, depth);
}
if (root->right){
depth ++;
travel_and_sum(root->right, sum, depth);
}
depth --;
}
int main(){
int amount;
cin >> amount;
_node* root;
_node heap_array[amount] = {};
for (int i = 0;i < amount; i ++){
int data;
cin >> data;
heap_array[i].data = data;
}
Heap<_node> heap_huff;
heap_huff.build(heap_array, amount);
_node *parent, *leftchild, *rightchild;
for (int i = 0; i < amount - 1; i ++){
leftchild = new _node(heap_huff.heapmin()); heap_huff.dlt(0);
rightchild = new _node(heap_huff.heapmin()); heap_huff.dlt(0);
parent = new _node;
parent->merge(*leftchild, *rightchild);
heap_huff.insert(*parent);
root = parent;
}
// bi tree travel to compute the sum of wl
int sum = 0;
int depth = 0;
travel_and_sum(root, sum, depth);
cout << sum;
return 0;
}