Python的heapify（）與列表理解和切片不兼容嗎？

我在一個程序中發現了一個有趣的錯誤，我有點懶惰地執行，並想知道我是否正確理解它。簡短版本是Python's heapq implementation實際上並沒有排序列表，它只是以堆爲中心的方式列出列表。具體而言，我期待heapify()產生一個有序列表，以有序的方式促進列表理解。使用Python的heapify（）與列表理解和切片不兼容嗎？

優先提示例如，Python的文檔：

from heapq import heapify, heappush, heappop 
from random import shuffle 

class Item(object): 
    def __init__(self, name): 
     self.name = name 

lst = [] 

# iterate over a pseudo-random list of unique numbers 
for i in sample(range(100), 15): 
    it = Item("Some name for %i" % i) 
    heappush(lst, (i, it)) 

print([i[0] for i in lst])

結果

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

此，我們注意到，不在列表的原排序，但顯然一些以堆爲中心的排序爲described here。我正在懶洋洋地期待這完全訂購。

作爲測試，通過heapify（）運行列表會導致沒有變化（如列表已經堆ishly訂購）：

heapify(lst) 

print([i[0] for i in lst]) 

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

而通過與訂貨的heappop()功能結果的列表迭代預期：

lst2 = [] 
while lst: lst2.append(heappop(lst)) 

print([i[0] for i in lst2]) 

>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97]

因此，它似乎heapq不下令列表（至少在這個詞的人的意義上），而是heappush()和heappop()功能能夠饒有興趣地列出堆。

結果：堆積列表上的任何切片和列表理解操作都會產生無序結果。

這是真的，這是總是是真的嗎？

（順便說一句：Python之3.0.1上的WinXP系統）

來源

2009-06-25 JohnMetta

堆不是排序列表（這是一個部分地排序的二進制樹的表示）。

所以是的，你是對的，如果你期望一個heapified列表行爲像一個排序列表，你會失望。關於堆的唯一排序假設是heap[0]始終是它的最小元素。

（這是很難多地增加你所編寫的程序 - 你的問題的事物如何是一個很好的書面記錄8-）

來源

2009-06-25 23:23:49 RichieHindle

是的，我主要發佈它，以便在其他人有同樣問題時可用，但很高興知道我誤解了這些文檔，並且應該更清楚地閱讀它們。 – JohnMetta 2009-06-26 14:48:41

其結果是：在任何切片和列表理解操作 heapified list將產生無序的結果。

這是真的，這是真的嗎？

如果你只是想獲得一個一次性的排序列表，使用：

myList.sort()

優先級隊列/堆可以被用來實現排序，或者它們可以被用來保持隊列優先形式。插入到堆中的是O（lg n），get是O（1），並且清除是O（lg n），這比僅僅一遍又一遍地遍歷整個列表好得多。

來源

2009-06-25 23:30:05

「」「我期待着heapify（）會產生一個有序的列表，以有序的方式促進列表理解。」「」：如果這個期望是基於手冊的閱讀，你應該提出一個文檔錯誤報告。

「」「結果：堆積列表上的任何切片和列表理解操作都會產生無序結果。這是真的嗎？」「」：就像random.shuffle（），所提及的活動未被定義爲產生「有序」結果。它可能偶爾產生「有序」的結果，但這是巧合，不值得信賴和不值得問（恕我直言）。

來源

2009-06-26 00:11:15

「結果：堆積列表上的任何切片和列表理解操作都會產生無序結果。這是真的嗎？這總是正確的嗎？」不，這並非總是如此。雖然大部分時間它都是無序的，但它可能會被訂購。 heapify（）生成一個滿足「heap不變量」的列表。在這種情況下，它是一個小堆。事實證明，排序列表還滿足堆不變量（請參見heapq段落4：「heap.sort（）維護堆不變量」）。所以在理論上，一個堆積列表也可能會被排序。

來源

2009-06-26 04:13:54 newacct

Python的heapify（）與列表理解和切片不兼容嗎？

回答

相關問題