Борюсь с этим вопросом на собеседовании. Любая помощь приветствуется

Question

Кодирование Хаффмана - это метод кодирования символов в зависимости от их частоты. Каждой букве назначается двоичная строка переменной длины, например 0101 или 111110, где более короткие длины соответствуют более общим буквам. Для достижения sh этого двоичного дерева строится такое, что путь от root к любому листу однозначно отображается на символ. При обходе пути спуск к левому дочернему элементу соответствует 0 в префиксе, тогда как спуск вправо соответствует 1.

Вот пример дерева (обратите внимание, что только у конечных узлов есть буквы):

        *
      /   \
    *       *
   / \     / \
  *   a   t   *
 /             \
c               s

В этой кодировке кошки будут представлены как 0000110111.

Учитывая словарь частот символов, постройте дерево Хаффмана и используйте его для определения соответствия между символами и их закодированными двоичными строками.

Answer 1

Шаги по построению Дерева Хаффмана

Входные данные представляют собой массив уникальных символов с указанием их частоты появления, а выходные данные - Дерево Хаффмана.

1. Создание листовой узел для каждого уникального символа и построить минимальную кучу всех конечных узлов (минимальная куча используется в качестве очереди с приоритетом. Значение поля частоты используется для сравнения двух узлов в минимальной куче. Первоначально наименее частый символ равен root)

2. Извлечь два узла с минимальной частотой из минимальной кучи.

3. Создать новый внутренний узел с частотой, равной сумме частот двух узлов. Сделайте первый извлеченный узел его левым дочерним элементом, а другой извлеченный узел - его правым дочерним элементом. Добавьте этот узел в минимальную кучу.

4. Повторяйте шаги 2 и 3, пока куча не будет содержать только один узел. Остающийся узел - это узел root, и дерево завершено.

Процедура построения дерева Хаффмана с примером

Посмотрите на в этом руководстве описывается пошаговая процедура построения дерева ..