使用分鐘和Maxes - Heapq適當？

Question

我有一個調度算法，其中我比較了優先級/任務元組列表的最小值和最大值，對它們進行了一些更改其優先級的操作，然後將它們重新插入到列表中並使列表適當更新。 heapq會是最好的數據結構嗎？我如何進行初始比較（基本上是確定優先級值是否足夠分開以便需要進一步操作;如果不是該功能將停止），而不彈出？一旦比較完成，我將如何將最大值與最小值一起計算，因爲heapq僅用於突出最小值？

Answer 1

heapq只提供最小堆 - 也就是說，您可以在O（log N）時間彈出min值，但不會輸出max值。

如果您想要一個類似於heapq的雙面數據結構，有幾個基本選項。

首先，常規最小堆有什麼問題？這不僅僅是API;找到最大值需要O(n)時間，而不是O(1)時間，因此彈出它需要O(n)而不是O(log n)，這是您想要改進的關鍵。

簡單的黑客攻擊包括保留兩個堆，一個是正常值，一個是正常值，因此它們向後排序。下面是僞代碼實現：

def push(self, value): 
    insert into both normal and reversed heaps 
def minpop(self): 
    check that the min value of normal hasn't reached the min value of reversed 
    pop and return the min value of normal 
def maxpop(self): 
    check that the min value of reversed hasn't reached the min value of normal 
    pop and return the min value of reversed 

乍一看，這似乎是每個操作的最壞情況下的行爲應該是正好兩倍於minheap的，但事實並非如此。特別是，最壞情況的空間是有史以來插入的元素的數量，這可能比插入的數字多兩倍 - 刪除的數字。 （例如，如果您插入了1000個項目並刪除了100，900 >> 200）。

有許多用例不適用，並且它應該很明顯，如果它不起作用用例。但是當它適合是時，它很簡單。

如果它不是合適，您可以使用真正的最小最大堆。這基本上只是將最小堆的normal和reversed版本交錯爲單個結構，並且可以輕鬆地在上面的「檢查」情況下做正確的事情（而不是將值留在後面）。

但是，如果您希望雙端優先級隊列具有對稱性能，那麼您實際上無法比平衡樹或跳過列表做得更好。 （好吧，不是爲了一般目的，如果你有特定的行爲特徵，那可能是不正確的。）AVL樹，紅黑樹和跳過列表的實現比min-max二進制堆多得多。因此，搜索「平衡樹」，「紅黑樹」，「AVL樹」，「跳過列表」等的PyPI和ActiveState配方，你會發現像bintrees和skiplist這些都應該工作。我想推薦blist。它使用一棵平衡樹和一個數組的特殊混合，而不是一個經過深入研究的數據結構，乍一看可能會讓你認爲它不太值得信賴。但是，我相信它比任何競爭模塊都有更多的使用和實際測試，並且它也經過了相當多的優化。 （在處理A * log Bn + C性能時，更改A或C通常比更改B更具影響力。）它也有一個很好的界面 - 實際上只有少數界面。如果您使用blist.sortedlist，則可以執行sl[0],sl[-1],sl.pop(0),sl.pop(-1)和sl.add(x)，幾乎完全如您所料。

因此，您的代碼會是這個樣子（如果我沒有理解你的英文說明）：

class MyQueue(object): 
    def __init__(self): 
     self.sl = blist.sortedlist(key=operator.itemgetter(0)) 
    def add(self, priority, task): 
     self.sl.add((priority, task)) 
    def step(self): 
     if self.sl[-1][0] - self.sl[0][0] < MyQueue.EPSILON: 
      return 
     minprio, mintask = self.sl.pop(0) 
     maxprio, maxtask = self.sl.pop(-1) 
     newminprio, newmaxprio = recalc_priorities(minprio, maxprio) 
     self.add(newminprio, mintask) 
     self.add(newmaxprio, maxtask) 

的問題與任何這些方法是，偷看雙方最壞的情況是O(log N)而非O(1) 。但有解決這個簡單的方法，如果這是唯一的操作，您需要：只要保持這些值緩存：

class MyQueue(object): 
    def __init__(self): 
     self.sl = blist.sortedlist(key=operator.itemgetter(0)) 
     self.minprio, self.maxprio = None, None 
    def add(self, priority, task): 
     self.sl.add((priority, task)) 
     if prio < self.minprio: self.minprio = prio 
     elif prio > self.maxprio: self.maxprio = prio 
    def step(self): 
     if self.maxprio - self.minprio < MyQueue.EPSILON: 
      return 
     minprio, mintask = self.sl.pop(0) 
     maxprio, maxtask = self.sl.pop(-1) 
     newminprio, newmaxprio = recalc_priorities(minprio, maxprio) 
     self.add(newminprio, mintask) 
     self.add(newmaxprio, maxtask) 
     self.minprio, self.maxprio = sl[0][0], sl[-1][0] 

這使得通過stepO(1)代替O(log n)快速路徑，並留下所有現有O(log n)操作仍O(log n)。

另請參閱Wikipedia，其中討論了可以替代二進制堆的其他類堆。最後

一個說明，這igorrs的評論提醒我：

有很多種不同的數據結構，將在這裏得到你同樣的最壞情況下的算法複雜度。有時，任何避免O(n)都足夠好，所以你應該用最簡單的實現去完成它。但有時（特別是對於許多操作，但小數據或非典型數據），常數因子，最佳情況等可以產生巨大的差異。在這種情況下，正確的做法是構建多個實現並測試真實數據，並查看最快的數據。

Answer 2

假設你正在考慮一個堆，我可以假設你的預期（與n爲元素的總數）爲：

1. 找到最小的密鑰和O(1)時間最大的關鍵。
2. 在O(log(n))時間內，用最小的鍵和具有最大鍵的元素重新插入（使用更改的鍵）。

這可以用min-max heap完成。不幸的是，我不認爲這在Python的標準庫中可用。

如果你放鬆了第一個要求，任何平衡樹（例如紅黑色）都可以實現，所有期望的操作都需要O(log(n))時間。

Python的標準庫也不提供任何平衡樹，所以你將不得不推出自己的或尋找一個實現。