如何使用数据结构与算法优雅地实现边统计边排序？

Question

我感觉对于关键字的统计和排序很多情况都是基于已经知道所有关键字的情况下进行哈希表统计然后排序。
但是假如我并不能事先知道有哪些关键字我只能一次一次得像开盲盒一样去获取关键字，并且每一次获取后我都要更新排序结果。
我想过如果用数组，每次获取关键词后查找倒是可以用二分查找实现O(logn)，当然也可以添加一个哈希表实现近似O(1)实现查找。如果关键字存在还好，顶多就是交换关键字位置，要是不存在就要进行新增元素并且移动了。
然后我就想用链表，每次获取一个关键字要么就是在链表头部增一个节点，要么就是把原来存在的关键字节点移动到出现次数加一的位置，至少新增或者移动复杂度是相较于数组是降低了。但是要找到存在的关键字节点的复杂度变成了O(n)。我觉得还是可以使用哈希表存储关键字和节点地址或者引用实现O(1)查找。
我还想到了个方案，用红黑树，但是红黑树我没听说过有更新操作，但可以用删除和新增两个操作来代替，但是感觉十分不优雅。
我想问到底最优雅的方法是啥？是不是本身就存在一个我还不了解的方案解决这个问题。

Answer 1

堆排序吧，或者二叉排序树，也就是你说的红黑树