huffman da depressão

// Classe nodo é a estrutura basica de cada nó presente na arvore de huffman
class NodoHuffman
{
	construtor()
	{
		// quantidade de vezes que aparece
		dados = 0;
		// caracter representado pelo nodo
		c = '';
		esquerda = vazio;
		direita = vazio;
	}
}

// função recursiva para printar o código de huffman, onde S é o código de huffman
funcao printCode(raiz, s)
{
	// caso base; se o nó esquerdo e direito são vazios então é uma folha e deve printar o código gerado pelo percurso da arvore.
	se (raiz.esquerda == vazio
		&& raiz.direita == vazio
		&& (raiz.c).paraLetraMinuscula() != (raiz.c).paraLetraMaiuscula()) {
	
		// c é o caractere no nó
		print(raiz.c + ":" + s + "\n");
	
		returna;
	}

	// se vamos para esquerda adicionamos '0' ao codigo
	// se vamos para direira adicionamos '1' ao código
	
	// chamada recursiva para a direita e esquerda das subarvores geradas.
	printCode(raiz.left, s + "0");
	printCode(raiz.right, s + "1");
}

contaFrequencia(palavra)
{
	defina dicionario = vector<caractere, inteiro>([]);
	
	for(defina i = 0; i < palavra.tamanho; i++){
		for(defina j = 0; j < dicionario.tamanho + 1; j++){
			se(j == dicionario.tamanho+1){
				dicionario.insere(palavra[i], 1)
				// sai do laço de repeticao
				sair;
			}senao se(dicionario[j][0] == palavra[i]){
				dicionario[i][1] = dicionario[i][1] + 1;
			} 
		}
	}

	retorna dicionario.ordena(funcao(a,b){retorna a[1]-b[1];});
}
	
// função principal
// numero de caracteres
	
	defina palavra = “Em rápido raptoum rápido rato raptou três ratos sem deixar rastros”.
	defina dicionario = contaFrequencia(palavra);
	defina n = dicionario.tamanho;
	
	// Criando uma fila de prioridades q.
	// criando um min-priority queur(min-heap)
	defina q = [];
	
	for (defina i = 0; i < n; i++) {
		// criando um nodo huffman através de um objeto
		// e adicionando na fila de prioridades
		defina hn = new NodoHuffman();
	
		hn.c = dicionario[0][i];
		hn.data = dicionario[1][i];
	
		hn.left = vazio;
		hn.right = vazio;
	
		// adiciona o nodo na fila
		q.push(hn);
	}
	
	// cria o nó raiz
	defina raiz = vazio;
	// ordena os valores
	q.ordena(funcao(a,b){return a.data-b.data;});
		
	// Extrai os dois menores valores
	// da heap até o tamanho ser igual a 1
	enquanto (q.tamanho > 1) {
	
		// menor elemento extraido
		defina x = q[0];
		q.remove();
	
		// segundo menor extraido.
		defina y = q[0];
		q.remove();
	
		// cria um novo nodo F
		defina f = new NodoHuffman();
		
		// soma a frequencia dos dois nodos e atribui ao nodo F criado
		f.data = x.data + y.data;
		// indica que não possui caractere
		f.c = '-';
		
		// primeiro nodo extraido se torna seu filho a esquerda
		f.left = x;
		
		// segundo nodo extraido se torna seu filho a direita
		f.right = y;
	
		// faz o nodo F como a raiz
		raiz = f;
	
		// adiciona o nodo F na fila de prioridades
		q.insere(f);
		q.ordena(funcao(a,b){return a.data-b.data;});
	}
	
	// print the codes by traversing the tree
	printCode(raiz, "");