电子交易中排名前K位的股票算法

Question

您在电子交易所工作。一整天，您都会收到由产品名称和股票交易量组成的报价（交易数据）。例如：{name: vodafone, volume: 20}

如果以下情况，您将维护什么数据结构：

• 您必须说出当天结束时按交易量计算的排名前k的产品。
• 您必须指出全天交易量最高的k产品。

您能想到的最有效的解决方案是什么？

我能想到的最有效的解决方案是在两种情况下都使用堆并映射

• 通过减少数量来堆存库存（更新-O(logn)和getTop k-O(k)）
• 映射以跟踪库存量（更新-O(1)）

Answer 1

您正在寻找的是一种地图或词典，它支持以下查询：

• [Add(key, x)：将x添加到该键的总数中，如果尚不存在，则创建一个新条目。
• GetKLargest(k)：返回最大k个条目的键/总计。

让我们说Q是查询数，而n是不同键的数。我们应该假设Q比n大得多；以纽约证券交易所为例，每天有几千只股票交易，每天有几百万笔交易。

---

在第一种情况下，我们假设存在大量的Add查询，然后是一个GetKLargest查询。由于Add查询的成本占主导地位，因此我们可以使用hashtable，以便Add花费O（1）时间，然后在一天结束时我们可以在O（n 使用大小为[[k的优先级队列记录log [[k）时间；请注意，我们不需要在O（n log n）时间内对整个键集进行排序，只需要查找最大的k个元素即可。回答Q查询的总成本为O（Q + n日志k）。

在第二种情况下，我们假设两种类型的查询都可能很多。任一查询的成本都可能占主导。一个不错的选择是使用GetKLargest，它在O（log

---

n）时间中支持order statistic tree，在O（

k

log n）时间中支持Add。要在树中按名称查找公司，需要一个单独的索引，该索引可以作为哈希表维护。在最坏的情况下，总成本为O（Qk log n）。如果

---

k是固定的或具有固定的限制，我们可以做得更好：将总数保留在哈希表中，但同时保留当前顶部

k

元素的优先级队列。由于维护优先级队列，GetKLargest查询的成本现在为O（log k）；为了有效地做到这一点，我们需要映射还将每个公司的当前索引存储在优先级队列中（如果有的话），否则，搜索合适公司的优先级队列为O（k）。 Add的成本为O（k），因为我们只输出优先级队列的内容。 （问题并不表示我们需要按顺序输出它们。如果这样做，则可以对优先级队列使用排序数组而不是堆，并且GetKLargest需要O（k）时间。 ）在这种情况下，回答Q个查询的总成本为O（

Qk

）。注意，这仅在我们事先知道查询到达之前可以查询的k的最大值时有效；否则我们不知道将优先级队列设为多大。