algorithm - 优先队列，其中值是两种货币的总和，popMin 采用汇率

Question

我想定义一个优先级队列，其中优先级具有两种不同货币的组件。例如，商品 A 的价格为 1 美元 + 20 日元。这个队列有两个方法，insert(priceInUsd, priceInYen) 和popMin(exchangeRate)，它以日元为单位的美元价格，弹出最低的项目根据此汇率，以美元和日元计的总成本。我该如何实现？

到目前为止，这是我的想法:

• 使用 k-d 树。插入需要 log(n)。我认为您可以通过对普通的 k-d 树最近邻算法进行微小修改来实现 findMin，因此据称这应该花费 log(n) 时间。维基百科对 k-d 树最近邻是否真的是 log(n) 如果你有糟糕的数据最坏的情况持谨慎态度，所以我不确定这一点。此外，我从未见过看起来特别可靠的消息来源声称 kd 树允许 log(n) 插入。
• 维护点的凸包，当你想得到最小值时，循环遍历其中的所有内容。最坏情况 n，但如果通常只有 n**(1/3) 东西在你的凸包中，这平均来说没问题。

Answer 1

在 dynamic planar convex hull 上有一些您没有提到的现有技术问题。 Brodal and Jacob (FOCS '02) 给出了一个数据结构，可以让你在一个方向上插入一个点，删除一个点，并在摊销的对数时间内找到一个方向的极值点，这足以实现你的数据结构(尽管实现看起来很复杂)。