如何改进我关于堆排序的Python代码？

Question

我试着自己编写堆排序程序Leetcode 217. Contains Duplicate，如下所示，而不是使用Python内置排序方法。 Leetcode应该接受堆排序方法，但由于某些原因，我不知道，虽然我的堆排序程序运行良好，但我仍然从Leetcode中得到运行时拒绝。谁能帮忙？

解决，下面的代码使用弗洛伊德算法来初始化堆重新编辑并已通过本文给出了

def heapsort(nums): 

    def swap(i, j): 

     nums[i], nums[j] = nums[j], nums[i] 


    def sift(start, size): 

     l = (start << 1) + 1 # Do not forget() for << 
     r = l + 1 
     largest = start 
     if l <= size - 1 and nums[start] < nums[l]: 
      largest = l 
     if r <= size - 1 and nums[largest] < nums[r]: 
      largest = r 
     if largest != start: 
      swap(start, largest) 
      sift(largest, size) 


    size = len(nums) 

    # Initialize heap (Floyd Algorithm) 
    end = (size >> 1) - 1 
    while end >= 0: 
     sift(end, size) 
     end -= 1 
    swap(0, size - 1) 
    size -= 1 

    # Heapify recursively 
    while size > 1: 
     sift(0, size) 
     swap(0, size - 1) 
     size -= 1 

Answer 1

你的代码太多了。您正在重建整个堆，并删除每个项目。那么O（n log 2）算法应该是O（n^2）。

从本质上讲，你的代码是这样做的：

while array is not empty 
    rearrange array into a heap 
    extract the smallest item 

重新排列堆取，充其量，O（n）的时间。并提取最小的需要O（log n）。所以你的算法是O（n^2 + n log n）。

实际上，你自下而上建立堆的方法本身就是O（n log n）。所以你的堆排序算法实际上是O（（n + 1）*（n log n））。无论如何，这是一个非常不理想的算法。

堆排序的想法是，你将数组排列成堆一次。这是一个O（n）操作。该算法非常简单：

for i = heap.length/2 downto 1 
    siftDown(i) 

这就是所谓的Floyd's algorithm，它的发明者之后。

请注意，我们开始在阵列的中间，并筛选下降。这个想法是最后的n/2项是叶节点，所以无论如何它们都不能筛选。从n/2开始向后，我们可以在O（n）时间内堆栈整个阵列。

的阵列被布置成堆之后，我们执行以下操作：

while heap is not empty 
    output the item at heap[0] 
    move the item at the end of the heap to heap[0] 
    reduce the count of items by 1 
    siftDown(0) 

在堆的项[0]是剩余的在堆的最小项目，所以我们将其输出。然后，不需要重建整个堆。你所要做的就是把堆中的最后一个物品放在最上面，然后把它放到一个位置。剩下的堆仍然有效。

进行这些更改会减少运行时间，但我不知道这是否会使您的代码可以接受。还有另一种方法来检查重复项。它需要O（n）额外的空间，但它比排序更快。

这个想法是创建一个哈希表，然后通过数组，检查项目是否在哈希表中。如果没有，请添加它。如果它已经在表格中，那么它是重复的。正如哈罗德指出的那样，Python有一种类型，使得这种事情很容易做到。

Answer 2

堆排序发言，考虑heapq蟒模块。它存在这个目的 - 提供堆队列算法的实现。它的设计不是非常方便，但有方便wrappers - 你可以自己谷歌。

说到找到重复项，任何n log(n)排序算法应该不够高效。看看python set builtin！