#include "stdafx.h"
#include "malloc.h"
#include"string.h"
typedef struct
{
int weight;
int parent, lchild, rchild;
}htnode,*huffmantree;
typedef char * *huffmancode;
void select(huffmantree &ht, int n, int *s1, int *s2)
{
int i = 1;
huffmantree p;
p = ht;
*s1 = 1;
*s2 = 2;
int s3, s4;
s3 = p->weight;
s4 = (p++)->weight;
if ((s4) < (s3))
{
s4 = s3;
s3 = p->weight;
}
p++;
while (i <= n)
{
if ((p->parent) != 0)
{
++p;
++i;
}
else
{
if (p->weight > s4)
{
p++;
i++;
}
else
{
*s2 = i;
p++;
i++;
}
}
}
}
void huffmancoding(huffmantree &ht, huffmancode &hc, int w, int n)
{
if (n < 1) return;
int m;
m = 2 * n - 1;
ht = (huffmantree)malloc((m + 1) * sizeof(htnode));
huffmantree p;
int i;
int s2;
int s1;
for (p = ht, i = 1; i <= n; ++i, ++p, ++w) *p = { *w,0,0,0 };
for (; i <= m; ++i, ++p) *p = { 0,0,0,0 };
for (i = n + 1; i <= m; ++i)
{
select(ht, n, &s1, &s2);
ht[s1].parent = i;
ht[s2].parent = i;
ht[i].lchild = s1;
ht[i].rchild = s2;
ht[i].weight = ht[s1].weight + ht[s2].weight;
}
hc = (huffmancode)malloc((n + 1) * sizeof(char));
char cd;
cd = (char)malloc(n * sizeof(char));
cd[n-1]= '\0';
i = 1;
for (; i <= n; ++i)
{
int start;
start = n - 1;
int c,f;
for (c = i, f = ht[i].parent; f != 0; c = f, f = ht[f].parent)
if (ht[f].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
hc[i] = (char*)malloc((n - start) * sizeof(char));
strcpy_s(hc[i], cd+start);
}
}
int main()
{
void select(huffmantree &ht, int n, int *s1, int *s2);
void huffmancoding(huffmantree &ht, huffmancode &hc, int *w, int n);
int n;
scanf_s("%d", &n);
int w[100];
int r = 0;
for (r = 0; r <= n - 1; r++)
scanf_s("%d", w[r]);
huffmantree ht;
huffmancode hc;
huffmancoding(ht, hc, w, n);
for (r = 1; r <= n; r++)
printf("%d", hc[r]);
return 0;
}
