Implement autocomplete with top-K suggestions

Implement an autocomplete component that, given a history of query strings with frequencies, returns the top K suggestions for an input prefix in real time. Support updates when a query is entered again (frequency increases) and insertion of new queries. Specify tie-breaking (e.g., higher frequency, then lexicographic), case-insensitivity and Unicode handling, and limits on K. Describe and implement the core data structures (e.g., trie with per-node top-K min-heaps or balanced trees), and analyze time/space complexity for insert, update, and query. Discuss how to handle deletions, streaming updates, and large-scale memory usage.