Top K 问题

问题描述

• 1.什么是 Top K 问题？简单来说就是在一堆数据里面找到前 K 大（当然也可以是前 K 小）的数。
• 2.可修改的Top K问题，数据数组内容可修改,每次修改后的Top K

分布式

面对海量数据，我们就可以放分布式的方向去思考了
我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据

堆排序

维护一个大小为 K 的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，只需要将堆顶元素与下一个数比较：如果大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。遍历完全部数据，Top K 的元素也自然都在堆里面了。

树状数组

快速选择算法

动态TOP K问题

问题描述

现在有一个无序序列，它里面的元素是动态变化的。也就是说我们随时可能会更改序列中的元素，包括增加，删除，修改元素。如果我们想要随时查询这个序列的第K大的值，该如何处理