使用堆的Soting列表？ Python

Question

衆所周知，堆是計算機科學研究中的一種排序機制。所以我想，如果我們可以使用Heap將數據分類到幾乎二叉樹類型的表單中。有沒有一種方法可以使用Heap將列表排序爲基本的升序或降序？

我認爲我們可以，但我不確定，因爲堆意味着以特定方式對數據進行排序。

但是你們怎麼看？你做了什麼？

謝謝

Answer 1

是的，你可以使用堆來排序你的值;只需從堆中彈出元素直到堆爲空;他們將按照排序順序返回：

from heapq import heappush, heappop 

def heapsort(iterable): 
    h = [] 
    for value in iterable: 
     heappush(h, value) 
    return [heappop(h) for i in range(len(h))] 

這是因爲heapq.heappop()保持堆不變。

請注意，這不是高效只是直接排序列表。此外，用於內置sorted()函數的TimSort算法是穩定;排序中具有相同值的元素保持相同的順序。 A heapsort()另一方面是不穩定的。