В любой момент нам нужно указать верхние k-продукты на основе количества

Question

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

Мой подход:

Поддерживать один minHeap размера К Поддерживайте один HashMap, который хранит идентификатор продукта в качестве ключа и продукта количества, индекс Heap в качестве значения.

Теперь получены одни данные, проверьте, присутствует ли идентификатор продукта в hashmap или нет.

Если присутствует в HashMap:

Обновление количество продукта в куче (Как будет увеличено количество продукта). Обновление нового количества, новый индекса в HashMap

Если нет в HashMap:

проверить, является ли больше минимальным значением в куче или нет нового количества продукта Если он больше, а затем удалить корень кучи и заменить на новое значение.

Проблема: Проблема с моим подходом заключается в том, что идентификаторы продуктов можно повторить в любое время, из-за которых количество продукта увеличится. Какой подход следует использовать, чтобы я мог хранить как количество продукта, так и индекс кучи, поскольку некоторые продукты в настоящее время могут быть не в куче, но в будущем они могут быть частью кучи.

Answer 1

Если у вас достаточно памяти для хранения всех продуктов и их количества, то сохраняйте хеш-карту с ключом продукта, а также древовидную структуру (например, AVL tree), упорядоченную по частоте.

Когда обновление приходит в:

• Если продукт не в хэш-карте, добавьте его в хэш-карте и добавить его к дереву с частотой 1.
• если продукт уже находится в хэш-карте, просматривает его в дереве, увеличивает его частоту и корректирует положение узла в дереве.

Добавление узла в дерево и настройка положения узла - это операции O (log n).

Когда вам нужно получить верхние «k» продукты по частоте, вы можете использовать обход дерева по порядку, с ранним выходом, когда вы достигнете k.

Если у вас нет памяти для хранения счетов для каждого продукта, все становится немного сложнее, и вам, вероятно, придется идти с алгоритмами аппроксимации. https://cstheory.stackexchange.com/questions/19802/top-k-frequent-items-in-data-stream дает некоторые идеи об этом.