Мне нужно хранить топ k наиболее часто встречающихся элементов в потоке. Для оценки частоты я использую алгоритмы count-min-sketch. Мой поток состоит из ключей (в виде строки). Таким образом, в основном каждый раз, когда я сталкиваюсь с новым ключом в своем потоке, я вычисляю частоту текущего ключа, просматривая структуру данных count-min-sketch. Однако я не могу хранить топ k наиболее часто используемых ключей.
Моей первой идеей было хранить их в мини-куче с фиксированным размером k. И я храню [частоту, ключ] внутри этой минимальной кучи с частотой компаратора. Таким образом, каждый раз, когда я получаю частоту ключа, я пытаюсь увидеть, превышает ли размер кучи k, если это так, тогда я сравниваю частоту текущего ключа с верхней (самой маленькой) частотой в минимальной куче, если мой текущий ключ Частота выше, чем когда я открываю верх и вставляю свой ключ в кучу.
Однако я понимаю, что min-heap - это не набор, что означает, что он допускает дублирование. Допустим, у меня есть очень горячая клавиша, и я продолжаю считать ее в потоке, поэтому каждый раз, когда я вставляю эту [частоту, ключ] в кучу, в итоге моя куча будет заполнена одним и тем же ключом, только разными частотами.
Так что мне интересно, есть ли хороший способ сохранить верхний k более частый элемент в count-min-sketch.