通過某些屬性Python堆積，屬性更改後重新堆疊

Question

我試圖使用python 3.5標準庫中的heappq模塊來創建相同類型的對象的優先級隊列。我希望能夠根據對象的屬性進行heapify，然後更改其中一些屬性的值，然後根據新值重新生成heapify。我想知道如何去做這件事。

import heappq 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 

queue = [multiNode(1), multiNode(2), multiNode(3)] 
heapq.heapify(queue) #want to heapify by whatever getKey returns for each node 
queue[0].setKey(1000) 
heapq.heapify(queue) #re heapify with those new values 

Answer 1

有多種方法可以讓你的代碼工作。舉例來說，你可以讓你的物品訂購通過實施一些rich comparison operator methods（也許使用functools.total_ordering來實現的其餘部分）：

@functools.total_ordering 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 
    def __eq__(self, other): 
     if not isinstance(other, multiNode): 
      return NotImplemented 
     return self.__key == other.__key 
    def __lt__(self, other): 
     if not isinstance(other, multiNode): 
      return NotImplemented 
     return self.__key < other.__key 

這將會使你的代碼的工作，但它可能不會是非常有效的reheapify您每次對其中的節點進行更改時都會排隊，特別是如果隊列中有很多節點。更好的方法可能是在隊列周圍編寫一些額外的邏輯，這樣就可以使隊列條目無效而不刪除它或違反heap屬性。然後，當您需要更新某個項目時，只需使其舊項目無效並添加一個具有新優先級的新項目即可。

下面是一個快速而髒的實現，它使用字典將節點實例映射到[pritority, node]列表。如果節點正在更新其優先級，則將檢查字典並將列表的node部分設置爲None。當從隊列的前面彈出節點時，無效條目將被忽略。

queue = [] 
queue_register = {} 

def add_to_queue(node) 
    item = [node.getKey(), node] 
    queue.heappush(queue, item) 
    queue_register[node] = item 

def update_key_in_queue(node, new_key): 
    queue_register[node][1] = None # invalidate old item 
    node.setKey(new_key) 
    add_to_queue(node) 

def pop_from_queue(): 
    node = None 
    while node is None: 
     _, node = heapq.heappop(queue) # keep popping items until we find one that's valid 
    del queue_register[node] # clean up our bookkeeping record 
    return node 

您可能需要測試這種情況，以防止重新確認，看看哪個程序實際使用隊列的速度更快。

你multiNode班上有幾個最後的音符（無關，你在你的問題在問什麼）：

有一些事情你在做類是不是很Python的。首先，Python最常用的命名約定對類使用CapitalizedNames，對幾乎所有其他（各種類型，函數，模塊的變量）使用lower_case_names_with_underscores。

使用雙引號下劃線__key的另一個問題。雙引導（而不是尾隨）unfrrore調用Python的名稱加密系統。這可能看起來像它的目的是使變量變爲私有的方式，但這不是真的。它更傾向於幫助防止意外的名稱衝突，例如當您在代理對象中設置屬性（否則模仿某些其他對象的屬性）或者在mixin類中（可能會被具有未知屬性的其他類型繼承）。如果班級以外的代碼確實想要訪問multiNode課程中的損壞屬性__key，則仍可以使用_multiNode__key來完成此操作。爲了提示意圖是一個私有屬性，您應該只使用一個下劃線_key。

這使我有權對我的最終問題，key可能不應該是私人的。使用getX和setX方法修改私有實例變量並不是非常晦澀難懂。記錄該屬性是該類公共API的一部分並讓其他代碼直接訪問該屬性更爲常見。如果您稍後決定在查找或修改屬性時需要執行某些操作，則可以使用property描述符將屬性訪問自動轉換爲對getter和setter函數的調用。其他編程語言通常以getter和setter開頭，而不是公共屬性，因爲稍後沒有更改屬性API實現的方式。所以無論如何，我會讓你的班級的__init__只設置self.key = keyValue，完全擺脫setKey和getKey！

Answer 2

做你要找的內容是使用dicts和Python的內置id()方法的粗暴的方式。這種方法基本上可以讓你把堆作爲你創建的對象的id堆，然後通過在dict中訪問它們來更新這些對象，其id是關鍵。我想這是我的本地機器上，似乎你在找什麼：

import heapq 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 

first_node = multiNode(1) 
second_node = multiNode(2) 
thrid_node = multiNode(3) 
# add more nodes here 
q = [id(first_node), id(second_node), id(third_node)] 
mutilNode_dict = { 
    id(first_node): first_node, 
    id(second_node): second_node, 
    id(third_node): third_node 
} 
heapq.heapify(q) 
multiNode_dict[q[0]].setKey(1000) 
heapq.heapify(q) 

heapify()不會真的做過多的在這裏，因爲對象的id將是相同的，直到它被刪除。如果您將新對象添加到堆並取出對象，它會更有用。