堆排序Python实现(Heap sort Python implementation)

def heap_sort(nos):
    global size
    size = len(nos)
    print "the size of the List is : %d " %size
    Build_heap(size,nos)
    for i in range(size-1,0,-1):
        nums[0],nums[i] = nums[i],nums[0]
        size = size-1
        print "\n", nums
        heapify(nos,i,size)
    print "heap sort array:" ,nums

def left_child(i):
    return 2*i+1

def right_child(i):
    return 2*i+2

def heapify(nums,i,size):
    l = left_child(i)
    r = right_child(i)
    if l <= size and r <= size:
        if r != size:
            if nums[l] >= nums[r]:
                max = nums[l]
                max_index = l
            elif nums[l] <= nums[r]:
                max = nums[r]
                max_index = r
            if nums[i] >= max:
                print nums
                return
            elif nums[i] <= max:
                nums[i],nums[max_index] = max,nums[i]
                heapify(nums,max_index,size)
        else:
            nums[i],nums[l] = nums[l],nums[i]
            print nums

# build a heap A from an unsorted array          
def Build_heap(size,elements):
    iterate = size//2-1
    for i in range(iterate,-1,-1):
        print "In %d iteration" %i
        heapify(elements,i,size)
    print "heapified array is : " ,elements


if __name__ == '__main__':
    #get input from user
    nums = [6,9,3,2,4,1,7,5,10]
    #sort the list
    heap_sort(nums)

输出我得到的是这样的：

the size of the List is : 9 
In 3 iteration
[6, 9, 3, 10, 4, 1, 7, 5, 2]
In 2 iteration
[6, 9, 7, 10, 4, 1, 3, 5, 2]
In 1 iteration
[6, 10, 7, 9, 4, 1, 3, 5, 2]
[6, 10, 7, 9, 4, 1, 3, 5, 2]
In 0 iteration
[10, 6, 7, 9, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
heapified array is :  [10, 9, 7, 6, 4, 1, 3, 5, 2]
heap sort array: 
[9, 7, 6, 4, 1, 3, 5, 2, 10]

我试图实现在python堆排序算法。 最终的输出是没有排序。 也有一些是错误的，我试图找出heapify操作，但我找不到它。

有人能说出什么是错在我的代码，并提出了它的解决方案？

Answer 1:

第一项（ 0 ）与最后一个项目swaped。 为了保持最大堆invairant，你应该叫heapify与0 。

def heap_sort(nos):
    size = len(nos)
    build_heap(size,nos)
    for i in range(size-1,0,-1):
        nums[0],nums[i] = nums[i],nums[0]
        size -= 1
        heapify(nos, 0, size) # <--- i -> 0

Answer 2:

以下是我的Python实现。 如果程序是“heapsort.py”，运行它是“蟒heapsort.py 10”，10个随机生成的数字进行排序的例子。

验证代码是靠近节目的结束，以验证功能的正确性，堆排序（）。

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, HeapSort
#
import sys, random


def pushdown( A, root, size_of_A ):
    M = root * 2
    if(M <= size_of_A):
        if(size_of_A > M):
            if(A[M - 1] < A[M]):
                M += 1

        if(A[root - 1] < A[M - 1]):
            A[root - 1], A[M - 1] = A[M - 1], A[root - 1]
            pushdown(A, M, size_of_A)


def heapsort( H ):
    for i in range(len(H)/2, 0, -1):
        pushdown(H, i, len(H))

    for i in range(len(H) - 1, 0, -1):
        H[i], H[0] = H[0], H[i]
        pushdown(H, 1, i)

    return H


number_to_numbers = int(sys.argv[1])
X = [ random.randint(0, number_to_numbers) for i in range(number_to_numbers) ]
Y = X
print Y
print heapsort(X)
print sorted(Y)

文章来源: Heap sort Python implementation