电子交易所Top K股算法
Algorithm for top K stock in electronic exchange
您在一家电子交易所工作。一整天，您都会收到由产品名称及其股票交易量组成的报价（交易数据）。例如：{name: vodafone, volume: 20}
如果出现以下情况，您将维护什么数据结构：
- 您必须告诉
k 交易日结束时交易量最高的产品。
- 您必须告诉
k 全天交易量最高的产品。
您能想到的最有效的解决方案是什么？
我能想到的最有效的解决方案是在这两种情况下都使用堆和映射
- 通过减少体积来存储库存的堆（更新 -
O(logn) 和 getTop k - O(k)）
- 跟踪库存量的地图（更新 -
O(1)）
您要查找的是一种支持以下查询的地图或字典：
Add(key, x)：将 x 添加到该键的总数中，如果尚不存在则创建一个新条目。GetKLargest(k): return k 个最大条目的 keys/totals。
假设 Q 是查询的数量，n 是不同键的数量。我们应该假设 Q 比 n 大得多；以纽交所为例，有几千只股票交易，每天有几百万笔交易。
在第一种情况下，我们假设有大量 Add 个查询，然后是一个 GetKLargest 个查询。由于 Add 查询的成本占主导地位，我们可以使用 hashtable 以便 Add 花费 O(1) 时间，然后在一天结束时我们可以做 GetKLargest 在 O(n log k) 时间使用大小为 k 的优先级队列；请注意，我们不需要在 O(n log n) 时间内对整个键集进行排序，只是为了找到 k 个最大的元素。回答 Q 查询的总成本是 O(Q + n log k ).
在第二种情况下，我们假设可能有大量的两种查询。任何一个查询的成本都可能占主导地位。一个好的选择是使用 order statistic tree，它在 O(log n) 时间内支持 Add，在 O(k log n) 时间。要在树中按名称查找公司需要一个单独的索引，该索引可以作为哈希表进行维护。在最坏的情况下，总成本为 O(Qk log n)。
如果k是固定的或者有固定的限制，我们可以做的更好：把总数放在一个hashtable里，同时也维护一个当前top的优先级队列k个元素并排。 Add 查询的成本现在是 O(log k) 因为维护了优先级队列；为了有效地做到这一点，我们需要地图也将每个公司的当前索引存储在优先级队列中，如果它存在，否则在优先级队列中搜索正确的公司是 O(k) . GetKLargest 的成本是 O(k) 因为我们只是输出优先级队列的内容。 （问题并没有说我们需要按顺序输出它们。如果我们这样做，那么我们可以使用排序数组而不是优先级队列的堆，并且Add需要O（k ) 次。)
在这种情况下，回答 Q 个查询的总成本是 O(Qk)。请注意，只有当我们在查询到达之前预先知道可以查询的 k 的最大值时，这才有效；否则我们不知道优先队列有多大。
您在一家电子交易所工作。一整天，您都会收到由产品名称及其股票交易量组成的报价（交易数据）。例如：{name: vodafone, volume: 20}
如果出现以下情况，您将维护什么数据结构：
- 您必须告诉
k交易日结束时交易量最高的产品。 - 您必须告诉
k全天交易量最高的产品。
您能想到的最有效的解决方案是什么？
我能想到的最有效的解决方案是在这两种情况下都使用堆和映射
- 通过减少体积来存储库存的堆（更新 -
O(logn)和 getTop k -O(k)） - 跟踪库存量的地图（更新 -
O(1)）
您要查找的是一种支持以下查询的地图或字典：
Add(key, x)：将 x 添加到该键的总数中，如果尚不存在则创建一个新条目。GetKLargest(k): return k 个最大条目的 keys/totals。
假设 Q 是查询的数量，n 是不同键的数量。我们应该假设 Q 比 n 大得多；以纽交所为例，有几千只股票交易，每天有几百万笔交易。
在第一种情况下，我们假设有大量 Add 个查询，然后是一个 GetKLargest 个查询。由于 Add 查询的成本占主导地位，我们可以使用 hashtable 以便 Add 花费 O(1) 时间，然后在一天结束时我们可以做 GetKLargest 在 O(n log k) 时间使用大小为 k 的优先级队列；请注意，我们不需要在 O(n log n) 时间内对整个键集进行排序，只是为了找到 k 个最大的元素。回答 Q 查询的总成本是 O(Q + n log k ).
在第二种情况下，我们假设可能有大量的两种查询。任何一个查询的成本都可能占主导地位。一个好的选择是使用 order statistic tree，它在 O(log n) 时间内支持 Add，在 O(k log n) 时间。要在树中按名称查找公司需要一个单独的索引，该索引可以作为哈希表进行维护。在最坏的情况下，总成本为 O(Qk log n)。
如果k是固定的或者有固定的限制，我们可以做的更好：把总数放在一个hashtable里，同时也维护一个当前top的优先级队列k个元素并排。 Add 查询的成本现在是 O(log k) 因为维护了优先级队列；为了有效地做到这一点，我们需要地图也将每个公司的当前索引存储在优先级队列中，如果它存在，否则在优先级队列中搜索正确的公司是 O(k) . GetKLargest 的成本是 O(k) 因为我们只是输出优先级队列的内容。 （问题并没有说我们需要按顺序输出它们。如果我们这样做，那么我们可以使用排序数组而不是优先级队列的堆，并且Add需要O（k ) 次。)
在这种情况下，回答 Q 个查询的总成本是 O(Qk)。请注意，只有当我们在查询到达之前预先知道可以查询的 k 的最大值时，这才有效；否则我们不知道优先队列有多大。