Мы можем использовать комбинацию структур данных. Hash_map для поддержания частотных отображений, где ключом является целое число, и значение указателя на узел «частоты», представляющий значение частоты, и набор целых чисел, имеющих одинаковую частоту. Частотные узлы будут поддерживаться в списке, упорядоченном по значениям частот.
Узел частоты может быть определен как
class Freq {
int frequency;
Set<Integer> values_with_frequency;
Freq prev;
Freq next;
}
Элементы HashMap будут тогда содержать записи вида
Entry<Integer, Freq>
Итак, для моментального снимка набора данных, такого как a,b,c,b,d,d,a,e,a,f,b, где буквы обозначают целые числа, будет выглядеть следующая структура данных:
c -----> (1, [c, e, f])
|
|
e --
|
|
f --
a -----> (3, [a, b])
|
|
b --
d --> (2, [d])
Узлы Freq будут поддерживаться в связанном списке, скажем freq_nodes, , отсортированными по значению частоты. Обратите внимание, что, как объяснено ниже, для сохранения списка, отсортированного по операциям добавления / удаления, не потребуется никакой операции log (n).
Способ выполнения операций add(x) и delete_max_freq() быть реализовано следующим образом:
add (x): Если x не найден в карте elements, проверьте, содержит ли первый элемент freq_nodes объект Freq с частотой 1 Если так, добавьте x к набору values_with_frequency объекта Freq. В противном случае создайте новый объект Freq с 1 в качестве значения частоты и x, добавленным к (теперь только один элемент) упакованному набору values_with_frequency
В противном случае (т. Е. Если x уже присутствует на карте elements ), следуйте указателю в значении записи, соответствующей элементам x в объекте Freq в freq_nodes, удалите x из поля values_with_frequency объекта Freq, отметив текущее значение частоты x, которое является значением elements.get(x).frequency (удерживайте это значение, скажем, F). Если набор values_with_frequency отображается пустым из-за этого удаления, удалите соответствующий узел из связанного списка freq_nodes. Наконец, если следующий узел Freq в связанном списке freq_nodes имеет частоту F + 1, просто добавьте x в поле values_with_frequency следующего узла. В противном случае просто создайте узел Freq, как это было сделано в случае несуществования узла Freq с частотой 1 выше.
Наконец, добавьте запись (x, Freq) на карту elements. Обратите внимание, что вся эта операция добавления (x) будет иметь значение O (1) во времени.
Вот пример последовательности операций add () с состоянием подпоследовательности данных структура.
добавить (а)
a -> N1 : freq_nodes : |N1 (1, {a}) | ( N1 is actually a Freq object)
добавить (б)
a -> N1 : freq_nodes : |N1 (1, {a, b}) |
b -> N1
добавить (a) В этот момент 'a' указывает на N1, однако его текущая частота равна 2, поэтому нам нужно вставить узел N2 рядом с N1 в DLL, после удаления его из values_with_frequency set из N1 * {{ , b}
a -> N2 : freq_nodes : |N1 (1, {b}) | --> |N2 (2, {a}) |
b -> N1
Интересно отметить, что каждый раз, когда мы увеличиваем частоту существующего элемента с F до F + 1, нам нужно сделать следующее
if (next node has a higher frequency than F+1 or we have reached the end of the list):
create a new Freq node with frequency equal to F+1 (as is done above)
and insert it next to the current node
else :
add ‘a’ (the input to the add() operation) to the ```values_with_frequency``` set of the next node
Операция delete_max_freq () будет просто включать удаление последней записи связанного списка freq_nodes и итерацию по ключам в набранном наборе values_with_frequency для удаления соответствующих ключей из elements карта. Эта операция заняла бы O (k) время, где k - количество элементов с максимальной частотой.