Есть несколько способов сделать то, что вы просите. Самое простое - просто пересчитывать верхние теги K каждый раз, когда вас спрашивают. То есть вы поддерживаете какую-то гистограмму, а когда кто-то запрашивает верхнюю букву K, вы запускаете алгоритм, который использует очередь с приоритетами, чтобы выяснить верхнюю букву K. Это имеет преимущество простоты, но требует времени.
Вы можете сохранить этот список верхней буквы K, если хотите, и всякий раз, когда обновляется какой-либо другой элемент, вы проверяете, не превышает ли его новое число значение для самого маленького элемента в верхней части K. Если это так, то замените этот самый маленький элемент на недавно обновленный. Это должно быть достаточно легко сделать со вспомогательной структурой данных. Основным недостатком здесь является память, необходимая для хранения копии лучших элементов K.
Еще один способ сделать это - сохранить вашу хэш-карту с подсчетами и дополнительный связанный список, который упорядочивает вещи по убыванию. Данные в хеш-таблице содержат ссылки на узлы связанного списка. Всякий раз, когда элемент обновляется, вы обновляете его количество, а затем сравниваете его с количеством элементов непосредственно перед ним в связанном списке. Если новое количество больше, чем количество предшествующего элемента, переместите элемент вверх в списке, чтобы сохранить его в порядке. Конечно, вам, возможно, придется перемещать его несколько раз. По сути, это сортировка вставок.
Преимущество такого подхода состоит в том, что верхние элементы K всегда находятся в начале списка. Недостатком является потенциальная производительность. Если у вас много предметов и ваш диапазон значений невелик, каждое обновление может стоить O (n) времени. Вы можете ускорить это до некоторой степени, отслеживая следующий более высокий элемент, так что, например, если имеется 100 элементов со счетом 1, у вас есть ссылка на последний элемент со счетом 2. Поэтому, когда вы увеличиваете количество элементов с номером 1, вам не нужно просеивать его через все элементы с номером 1. Это стоит вам больше памяти (в худшем случае O (n) памяти), но делает вставку O ( 1) и сохраняет список в порядке.
Существуют и другие возможности, которые делают компромисс между скоростью и использованием памяти. То, что вы выберете, зависит от того, сколько памяти вы хотите потратить и как быстро вы хотите, чтобы эта вещь была.