爲什麼我的heapsort不工作？

Question

我有這個python heapsort-code由僞代碼製作而成。

但它給出了錯誤的結果。

def heapSortUp(a):   
    heapifyUp(a, len(a)) 

    end = len(a)-1 
    while end > 0: 
     a[end], a[0] = a[0], a[end] 
     end -= 1 
     siftUp(a, 0, end) 
    return a 

def heapifyUp(a, count): 
    end = 1 

    while end < count: 
     siftUp(a, 0, end) 
     end += 1 

def siftUp(a, start, end): 
    child = end 

    while child > start: 
     parent = int(math.floor((child-1)/2))  # floor = abrunden 

     if a[parent] < a[child]: 
      a[parent], a[child] = a[child], a[parent] 
      child = parent 
     else: 
      return 

我特別想使用siftUP版本。

通過計算print heapSortUp([1,5,4,2,9,8,7]) 返回：[8, 7, 9, 2, 1, 4, 5, 7, 5]

Answer 1

的問題是，你需要篩選下來heapSortUp(a)

def heapSortUp(a):   
    heapifyUp(a, len(a)) 

    end = len(a)-1 
    while end > 0: 
     a[end], a[0] = a[0], a[end] 
     end -= 1 
     siftDown(a, 0, end) 
    return a 

你需要篩選下來的原因是不起來，因爲篩選了無效堆。這可以用一個簡單的例子來展示。

堆堆4,3,2,1。經過一次迭代後，您將在末尾放置4個，在前面放置1個。因此，堆看起來像這樣的樹

1 
3 2 

然而，當您篩選了你交換1和2。這意味着2的優先級高於3.如果繼續進行排序（按照寫入的順序排列），您將向上排列1,3,2,4

要得到實際的排序，需要篩選出一個，以便堆看起來像在第一次迭代之後。

3 
1 2 

我離開了siftDown實現給你。

Answer 2

對於升序堆排序，你可以使用此代碼：

def heapSort(a): 
    count = len(a) 
    heapify(a, count) 

    end = count-1 
    while end > 0: 
     a[end], a[0] = a[0], a[end] 
     end = end - 1 
     siftDown(a, 0, end) 


def heapify(a, count): 
    start = math.floor((count - 1)/2) 

    while start >= 0: 
     siftDown(a, start, count-1) 
     start = start - 1 

def siftDown(a, start, end): 
    root = start 

    while root * 2 + 1 <= end: 
     child = root * 2 + 1 
     swap = root 
     if a[swap] < a[child]: 
      swap = child 
     if child+1 <= end and a[swap] < a[child+1]: 
      swap = child + 1 
     if swap != root: 
      a[root], a[swap] = a[swap], a[root] 
      root = swap 
     else: 
      return 

或者您可以使用此代碼：

def heapSortDown(lst): 
    for start in range(math.floor((len(lst)-2)/2), -1, -1): 
    sift(lst, start, len(lst)-1) 

    for end in range(len(lst)-1, 0, -1): 
    lst[end], lst[0] = lst[0], lst[end] 
    sift(lst, 0, end - 1) 
    return lst 

def sift(lst, start, end): 
    root = start 
    while True: 
    child = root * 2 + 1 
    if child > end: break 
    if child + 1 <= end and lst[child] < lst[child + 1]: 
     child += 1 
    if lst[root] < lst[child]: 
     lst[root], lst[child] = lst[child], lst[root] 
     root = child 
    else: 
     break 

和對於Decending：

def heapSortDown(lst): 
    for start in range(math.floor((len(lst)-2)/2), -1, -1): 
    sift(lst, start, len(lst)-1) 

    for end in range(len(lst)-1, 0, -1): 
    lst[end], lst[0] = lst[0], lst[end] 
    sift(lst, 0, end - 1) 
    return lst 

def sift(lst, start, end): 
    root = start 
    while True: 
    child = root * 2 + 1 
    if child > end: break 
    if child + 1 <= end and lst[child] > lst[child + 1]: 
     child += 1 
    if lst[root] > lst[child]: 
     lst[root], lst[child] = lst[child], lst[root] 
     root = child 
    else: 
     break