(Python) 非递增顺序排序的 Heapsort 最小堆实现。我究竟做错了什么？

Question

def min_heapify(A,k, n):
    left = 2*k +1
    right = 2*k +2
    n=int(len(A))
    if left < n and A[left] < A[k]:
        smallest = left
    else:
        smallest = k
    if right< n and A[right] < A[smallest]:
        smallest = right
    if smallest != k:
        A[k], A[smallest] = A[smallest], A[k]
        min_heapify(A, smallest, n)


def build_min_heap(A):
    n = int((len(A)//2)-1)
    for k in range(n, -1, -1):
        min_heapify(A,k,n)

def heapsort(A):
    n= int(len(A)) 
    build_min_heap(A)
    for i in range(n-1, 0, -1):
        A[i], A[0] = A[0], A[i]
        min_heapify(A, i, 0)


A = [8,7,9,1,4,6,3]
heapsort(A)
print(A)

我得到的输出是：[4, 3, 1, 8, 6, 9, 7] 我希望数组或列表按非递增顺序排序，构建了我的 min_heapify， build_min_heap 函数甚至 heapsort 函数都像默认的伪代码。我在这里做错了什么？请帮帮我

Answer 1

有几个错误。

首先，min_heapify不能使用n=int(len(A))，它必须尊重传入的堆的大小。否则，在算法的第二阶段，它会在已排序元素所在的数组，将它们吸收回堆中。

但是，first-and-a-half，当它被修复后，build_min_heap 不再构建 min-heap。那是因为它传递了错误的大小：它传递了 n，但是 n 在那个上下文中 小于堆大小的一半。以前第一个错误会对此进行补偿，但现在不会了。解决方案：将 len(A) 作为大小传递给这里。

其次，在算法的第二阶段，min_heapify(A, i, 0) 调换了第二个和第三个参数。当然，i 是堆的大小，0 是要堆化的索引，但它们是相反传递的：堆化项 i of a 0-size heap doesn't甚至说得通。

在我修复了这些东西之后，我得到了正确的结果，但我不敢说现在的代码是bug-free，代码中可能还隐藏着一些我没有找到的东西.

Answer 2

arr = [3,4,5,1,2,3,0,7,8,90,67,31,2,5,567]
# max-heap sort will lead the array to assending order
def maxheap(arr,p):
    
    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i+1)//2 - 1
            
            while arr[child]> arr[parent] and child !=0:
                arr[child], arr[parent] = arr[parent], arr[child]
                child = parent
                parent = (parent+1)//2 -1
                
    
def heapsort(arr):
    for i in range(len(arr)):
        maxheap(arr,i)
        arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1],arr[0]
        
    return arr
        

print(heapsort(arr))

看到这个我认为它会对你有所帮助

Answer 3

arr = [3,4,5,1,2,3,7,8,90,67,31,2,5,567]

# inheap_sort will lead the array to descending order using min heap
def minheap(arr,p):
    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i+1)//2 -1
            while arr[parent]>arr[child] and child !=0:
                arr[parent],arr[child]=arr[child],arr[parent]
                child = parent
                parent = (parent+1)//2 -1
                

def heapsort(arr):
    for i in range(len(arr)):
        minheap(arr,i)
        arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1], arr[0]
    return arr

print(heapsort(arr))

此方法适用于最小堆

(Python) 非递增顺序排序的 Heapsort 最小堆实现。我究竟做错了什么？

(Python) Heapsort min heap implementation for Non Increasing Order Sorting. What am I doing wrong?

python

sorting

algorithm

heap

heapsort