При повторной вставке в очередь - код Хаффмана

Question

Пример

3  2  5  5  
a  b  c  d

Соединение первых двух

   5         |  5   5
3     2      |  c   d
a     b      |

Я должен поставить новое дерево из пяти в очередь. Должен ли я поставить его в конец следующим образом:

5  5   5
c  d  / \
      3 2
      a b

Или я могу поставить это в начале:

   5    5  5
  3 2   c  d
  a b

Или даже в середине 'c' и 'd'

Это мой выбор илиесть ли правило?

Answer 1

Да, это ваш выбор.Каким бы способом вы не получили оптимальный код Хаффмана, даже если два результирующих кода могут явно различаться.

Вы можете получить:

a - 00
b - 01
c - 10
d - 11

или вы можете получить:

a - 111
b - 110
c - 10
d - 0

Теперь, если я умножу количество бит в каждом символе на количество вхождений, я получу для первого кода: 2 * 3 + 2 * 2 + 2 * 5 + 2 * 5 = 30 бит.Для второго кода: 3 * 3 + 3 * 2 + 2 * 5 + 1 * 5 = 30 бит.Таким образом, оба кода будут кодировать исходное сообщение с точностью до 30 бит.

Answer 2

Это не ваш выбор, очередь должна быть отсортирована всегда (по количеству вхождений и в случае равного количества вхождений по глубине дерева).Поэтому его нужно вставить в том месте, где он принадлежит.

Это необходимо для выбора поддеревьев с наименьшим количеством вхождений и, если есть выбор, наиболее мелкого из них, просто щелкаяих.

Если вы просто прибегаете к помощи после каждой вставки (это неэффективно и не следует делать), позиция, очевидно, не имеет значения.