堆排序Python实现

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)

输出，我得到的是这样的：堆排序Python实现

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操作有什么问题，但我找不到它。

有人可以指出我的代码中出现了什么问题并提出了解决方案吗？

来源

2013-07-01 vr22

临提示：Python可以分配给两个变量与一个操作：'NUMS [I]，NUMS [MAX_INDEX] = max时，NUMS [I]'和'NUMS [I]，NUMS [1] = NUMS [l]，nums [i]'。 –

Thanks。编辑上面的代码 – vr22

的第一个项目（0）与最后一个项目swaped。为了保持最大堆容量，你应该使用0来称呼heapify。

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

来源

2013-07-01 08:24:50 falsetru

为什么我的上面的代码不起作用，如果我给列表的输入列表像nums = [[5,10,15,20]，[6,3,16,19]，[2 ，9,26,40]，[8,22,23,24]]' – vr22

你想让你的代码作为输出产生什么？如果你想'[2,3,5,6,8,9，.....]'，将列表展平到第一维。 – falsetru

假设上面的代码用于构造k-路合并排序实现中的min-heap，将k-sorted子列表作为input.am，将k-排序的子列表存储在列表中。在那种情况下它不起作用 – vr22

以下是我的PYTHON实现。如果程序是“heapsort.py”，运行它的例子是“python 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)

来源

2016-01-20 22:39:30 user5818263

堆排序Python实现

回答

相关问题