有多個鍵的高效優先級隊列？

Question

我遇到了一個問題，我很確定有人已經遇到並解決了問題，但我找不到解決方案。

我有一些對象，每個對象都有幾個鍵。說：

• （1，2）：甲
• （3,3）:B
• （4,4）C：
• （5，1）：d

我需要一個「優先級隊列」式的數據結構，它可以讓我有效地按照每個鍵的優先級分別返回對象。例如，如果我通過第一個鍵返回它們，我會得到（A，B，C，D），通過第二個鍵，我會得到（D，A，B，C）。但是，我也需要能夠混合。例如，通過鍵返回，從第一個鍵開始，給我（A，D，B，C）。顯然，用第一個鍵彈出一個對象應該刪除第二個鍵。

一個天真的解決方案是在更改查找鍵時使用數據，但對於我的目的來說太慢了。另一種方法是使用堆並遍歷每個對象的另一個堆，但據我所知，這也很慢。是否有一個有效的優先級隊列算法，可以讓我通過多個不同的鍵刪除對象？

如果有一個python的實現它會非常好，但算法將是一個非常好的開始。

Answer 1

我認爲最好的辦法是爲每個鍵都有一個單獨的堆。當你移除一個堆的第一個元素時，你不能從其他堆中有效地移除它，但是你可以用某種方式「標記」它（例如通過改變它，或者如果可以將它添加到set）如果它最終會在別的地方再次出現，它可以被忽略。

這可能會讓你的堆膨脹一點，因爲它會保留無用的值，但我認爲它仍然比刪除和重新排序快得多。