如果我有 alist并且需要對其進行排序，是否有充分的理由使用list.sort()over heapq.heapify(list)，因為heapifyis O(N)( link ) 和.sort()is O(NlogN)？
如果 heapify 更快，為什么默認排序演算法 heapify 不是？
uj5u.com熱心網友回復：
正如人們在評論部分所說，“heapify”重新排列串列的元素以形成面向堆的二叉樹。
糟糕的排序通常使用 O(n * n) 來完成，所以使用 O(n * logn) 會更快。大多數好的排序庫都在 n * logn 時間內進行排序。
您可以使用堆在 n*logn 時間內對陣列進行排序，例如：
import heapq
a = [3, 6, 1, 3, 7, 9]
def sort_with_heap(a):
"""
sort O(nlogn)
"""
heapq.heapify(a) # heapify's the list O(n)
while len(a) > 0: # O(n) times
yield heapq.heappop(a) # O(logn)
print(list(sort_with_heap(a)))
>> [1, 3, 3, 6, 7, 9]
注意：上面的例子是為了理解堆如何用于排序，并不是空間最優的。要使用堆進行正確排序，請查看 heapsort（它適用于面向最大值的堆）并且不使用比排序陣列本身更多的空間。我自己在這里寫了一篇。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/530668.html
標籤：Python排序
上一篇：常用的正則運算式
下一篇：如何在R中分割整數向量