堆排序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實現

回答

相關問題