Design a data structure for dynamic top‑K frequency

Design a data structure that maintains a multiset of integers and supports the following operations efficiently:

Operations

• insert(x): Add one occurrence of value x.
• remove(x): Remove one occurrence of value x if it exists (if x is not present, do nothing).
• topK(k) -> List[int]: Return the k most frequent values currently in the multiset.

Requirements / Clarifications

• Frequency means the current count of each value in the multiset.
• If fewer than k distinct values exist, return all distinct values.
• If multiple values have the same frequency, you may return them in any order (or state and implement a deterministic tie-break such as smaller value first).
• Discuss time and space complexity for each operation.
• Explain why your chosen data structures are appropriate compared with alternatives (e.g., sorting on every query, balanced BST/TreeMap, etc.).
• Consider edge cases (removing down to zero, repeated inserts/removes, large k, empty structure).
• Bonus discussion: how would your approach change if the number of total updates is extremely large (e.g., up to billions)?

Dynamic Top-K Frequency Queries

You are given two parallel arrays, operations and values, that describe actions on an initially empty multiset of integers. Process the actions in order and return the result of every topK query.

Operations:

• insert(x): add one occurrence of integer x.
• remove(x): remove one occurrence of x if it exists; otherwise do nothing.
• topK(k): return the k most frequent distinct values currently in the multiset.

For this problem, topK(k) must return values ordered by:

1. higher frequency first
2. if frequencies are equal, smaller value first

If fewer than k distinct values exist, return all distinct values. A value whose count becomes zero should no longer appear in future results.

Your function should return a list containing the answer for each topK operation, in the order those queries appear.

An efficient solution is required; recomputing and sorting all frequencies on every query will be too slow for the given constraints.

Constraints

• 1 <= len(operations) == len(values) <= 200000
• operations[i] is one of "insert", "remove", or "topK"
• -10^9 <= values[i] <= 10^9 for insert/remove operations
• 1 <= k <= len(operations) for topK operations
• Tie-breaking for equal frequencies must be deterministic: smaller value first

Examples

Example 1

Input: (["insert", "insert", "insert", "insert", "insert", "topK", "remove", "topK"], [5, 7, 5, 7, 5, 2, 5, 2])
Output: [[5, 7], [5, 7]]

Explanation: After five inserts, frequencies are {5: 3, 7: 2}, so top 2 are [5, 7]. After removing one 5, frequencies become {5: 2, 7: 2}; tie is broken by smaller value first, so [5, 7].

Example 2

Input: (["insert", "insert", "insert", "remove", "topK", "remove", "topK"], [-1, -2, -1, -3, 3, -1, 3])
Output: [[-1, -2], [-2, -1]]

Explanation: Removing -3 does nothing because it is absent. First query sees {-1: 2, -2: 1}. After removing one -1, both values have frequency 1, so smaller value -2 comes first.

Hints

1. Use a hash map to store the current frequency of each value. Then think about a data structure that can quickly expose the highest-frequency candidates.
2. A max-heap with lazy deletion works well: push updated snapshots into the heap, and when answering topK, discard heap entries that no longer match the current frequency.