[DS-Для чайников] Куча 2

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

Мы продолжим с некоторыми вариантами использования или вопросами интервью, связанными с кучей.

Слияние K отсортированных массивов (разного размера)

Это известный вопрос интервью.

input = {1, 3, 9, 12}, {2, 6, 10, 14, 15}, {4, 7, 8, 13}, {5, 9, 11}
output = {1,2,3,4,5,6,7,8,9,9,10,11,12,13,14,15}

Решение 1. Наивный подход

Мы создаем массив для хранения результата, помещаем один за другим элементы массива в этот результат и используем любой алгоритм сортировки для сортировки результатов. этот подход будет иметь сложность O (NlogN), где N - общий элемент массивов списков.

Решение 2. Используйте приоритетную очередь

Идея в том, что мы используем приоритетную очередь для поддержания порядка элементов в массиве K.

input = {1, 3, 9, 12}, {2, 6, 10, 14, 15}, {4, 7, 8, 13}, {5, 9, 11}
Step 1 : Create Queue with size = k . We interator through K Array and put their first element to the Queue . We got 
                   Queue = {1,2,4,5} .
Step 2 : We poll the minimum element out of the queue and put to result .
                   Queue = {2,4,5}
                   Result = {1}
Step 3 : Put the second element of first array to the queue
                   Queue = {2,3,4,5}
                   Result = {1}
Step 4 : Repeat Step 2 
                   Queue = {3,4,5}
                   Result = {1,2}
Step 5 : Repeat Step 3 but change the first array to second array
                   Queue = {3,4,5,6}
                   Result = {1,2}
Step xxx : ... Repeat Step 2 and 3 but change the element index and array index . I think you already know how to play the game .

Поскольку мы должны перебрать все элементы, поэтому мы получили O (N), но каждый элемент, который нам нужен, помещается () в приоритетную очередь, это действие занимает O (LogK), где K - общий массив. Таким образом, это решение имеет сложность O (NLogK).

Кодирование Хаффмана

Кодирование Хаффмана — это алгоритм сжатия данных. Он основан на частом появлении символа или элемента в тексте или списке.

Пример: kaangnnggg

Номер символа по порядку

g -> 4 | n->3 | a->2 | h->1| k->1

это означает, что символ g появляется в тексте 4 раза.

Символ ASCII в 8-битной кодировке ASCII составляет 8 бит.

Символ Unicode в кодировке UTF-32 всегда имеет длину 32 бита.

…..

Пример: наш персонаж os занимает 8 бит памяти. Таким образом, с помощью g с потерянными 32 битами можно сохранить 4 символа g. Если мы сможем преобразовать g, станет 1 бит. поэтому мы можем сохранить 32–4 = 28 бит

g = 01100111-> g = 0;

n = 01101110 -> n = 1;

a = 01100001 -> a = 11;

h = 01101000 -> h = 100;

k = 01101011 -> k = 101;

поэтому khaangnnggg будет закодирован как 101|100|11|11|1|0|1|1|0|0
0 . Но настоящая проблема заключается в расшифровке. если мы декодируем биты 1011001111101100 . Это приведет ко многим результатам.

1|0|1|100|1|1|11|0|1|100 -> нгнхннагнх

и так далее

У нас есть правило, согласно которому ни один код не является префиксом другого кода. Под кодом мы подразумеваем биты, используемые для определенного символа. С приведенным выше примером. n является префиксом a или h или k . мы можем исправить приведенный выше пример с помощью

g = 0

n = 10

a = 110

h = 1110

k = 1111

поэтому khaangnnggg будет закодирован как 1111|1110|110|110|10|0|10|10|0|0|0 . Мы можем декодировать его с помощью приведенной выше карты кода, не думая о двусмысленности.

Как создать карту кода

Мы используем двоичное дерево узлов, когда левый дочерний элемент представляет бит «0», а правый дочерний элемент представляет бит «1».

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

Ввод: карта‹char,int› = {g=4,n=3,a=2,h=1,k=1}

Шаг 1. Преобразуйте каждый элемент карты в узел дерева.

Шаг 2. Поместите все узлы дерева в приоритетную очередь, отсортированную по частоте появления.

pq = {k=1,h=1,a=2,n=3,g=4}

Шаг 3. Извлеките 2 узла дерева из очереди.

h=1 , k=1

pq = {a=2,n=3,g=4}

Создайте новый внутренний узел из узла дерева выше 2, и он также является их родителем, внутренний узел не представляет ни одного символа, но имеет свой вес, который рассчитывается по сумме весов узла дерева выше 2.

внутренний (вес) = h(вес) + k(вес) = 1 + 1 = 2

Мы связываем или указываем левый дочерний элемент внутреннего узла на k и правый дочерний элемент внутреннего узла на h.

Шаг 4. Мы помещаем внутреннее значение в очередь.

pq = {внутреннее = 2, a = 2, n = 3, g = 4}

замените шаг 3 и шаг 4, пока queue.size =1 ;

Шаг 5: вытащите последний элемент из очереди. Это корень нашего дерева. начинаем делать код для каждого листа. С левым дочерним элементом мы помечаем его битом «0» и битом «1» для правого дочернего элемента.

мы путешествуем от корня к листовому узлу и собираем их код