MO417 - Questão para a prova oral

Número: 090

Enunciado:
Considere o algoritmo guloso de Huffman abaixo:

    HUFFMAN(C)
    1 n ← |C|
    2 Q ← C  // Inicializa fila de prioridades Q
    3 for i ← 1 to n-1 do
    4   alocar um novo nó z
    5   esquerda[z] ← x ← EXTRACT_MIN(Q)
    6   direita[z] ← y ← EXTRACT_MIN(Q)
    7   f[z] ← f[x] + f[y]
    8   INSERT(Q, z)
    9 return EXTRACT_MIN(Q)
em que:
C é um conjunto que contém n caracteres e que cada caractere c ∈ C tem frequência definida f[c], e
Q é uma fila de prioridade mímina, tendo f como chave.

Suponha que se deseja alterar o algoritmo de forma que, em vez de gerar um código de prefixo
que atribua palavras de código curtas a caracteres mais frequentes e palavras de código longas
a caracteres menos frequentes, ele passe a gerar um código que faça o contrário: atribua palavras
longas aos mais frequentes e curtas aos menos frequentes.
Para isso, as alterações necessárias no algoritmo seriam:
  1. Alterar as linhas 5 e 6, respectivamente, para:
        5   direita[z] ← x ← EXTRACT_MIN(Q)
    6   esquerda[z] ← y ← EXTRACT_MIN(Q)
  2. Utilizar Q como uma fila de prioridade máxima e alterar todas as chamadas a
    EXTRACT_MIN(Q) (nas linhas 5, 6 e 9) para EXTRACT_MAX(Q).
  3. Alterar a linha 7 para:
        7   f[z] ← f[x] - f[y]
  4. Apenas alterar a linha 9 para:
        9 return EXTRACT_MAX(Q)
  5. NDA

Autor(a): Fábio de Souza Azevedo