Design a data structure supporting insert, delete, and query Top-K frequent elements

Problem: Design a data structure supporting insert, delete, and query Top-K frequent elements Design a data structure that maintains frequencies of keys (integers or strings) under dynamic updates, and can return the current Top K most frequent keys at any time. Required operations Implement the following (or equivalent) APIs: insert(x): Insert key x (increment x's frequency by 1). delete(x): Delete one occurrence of x (decrement x's frequency by 1). If x does not exist (or its frequency is already 0), define the behavior clearly: you may ignore the operation or return an error/flag (but you must state it). When the frequency of x drops to 0, remove it from the structure. topK(): Return the current K most frequent keys (return all keys if fewer than K exist). Ordering: sorted by frequency descending; tie-breaking can be unspecified or explicitly defined. I/O convention (for an online-coding style prompt) You are given an integer K, followed by a sequence of operations. Output the result for each topK() call. Constraints Number of operations: 1 <= Q <= 2 * 10^5 Number of distinct keys: 1 <= U <= 2 * 10^5 1 <= K <= U You must analyze and explain: Time complexity per operation Space complexity Edge cases (deleting a missing key, K larger than the current number of keys, etc.) Example Let K = 2, operations: insert(a) insert(b) insert(a) topK() → expected [a, b] (a:2, b:1) delete(a) topK() → expected [a, b] (a:1, b:1, order may vary) delete(a) topK() → expected [b] Follow-up directions to be ready for Why HashMap + Min-Heap (or another structure) instead of sorting every time or using a TreeMap. How to optimize complexity and handle stale heap entries correctly (e.g., lazy deletion). How to handle huge-scale data (10^8+ events) when memory is limited (sharding, streaming TopK, approximate methods, etc.). Example Input K=2 ops: insert a, insert b, insert a, topK Output [a, b]