婴儿车堆分类

Question

下面是我对堆排序的尝试，它应该类似于从第152页开始在CLRS中显示的内容。

如果传递A= 9，0，5，7，4，6，3，8，1，2作为输入。BuildMaxHeap的输出是9，8，6，7，4，5，3，0，1，2，这似乎是正确的。然而，将相同的输入传递给HeapSort会给出9、8、4、7、2、3、5、6、1、0，这是完全错误的。

有人能对我做的错事指指点点吗？

def left(i):
    return 2 * i

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

def HeapSize(A):
    return len(A) - 1 

def MaxHeapify(A, i): 
    l = left(i)
    r = right(i)
    if l <= HeapSize(A) and A[l] > A[i]:
            largest = l 
    else:
            largest = i 
    if r <= HeapSize(A) and A[r] > A[largest]:
            largest = r 
    if largest != i:
            A[i], A[largest] = A[largest], A[i]
            MaxHeapify(A, largest)

def BuildMaxHeap(A):
    for i in range(HeapSize(A) // 2, 0, -1):
            MaxHeapify(A, i)

def HeapSort(A):
    BuildMaxHeap(A)
    for i in range(HeapSize(A), 1, -1):
            A[i], A[1] = A[1], A[i]
            MaxHeapify(A, 1)

Answer 1

正如我所看到的，对您的原始代码进行了一些更正(请参阅注释)：

def left(i):
    return 2 * i      # this is 1-based tree. Since your first element is stored in 0th cell, here is an error

def right(i):
    return 2 * i + 1    # same, this's 1-based

def HeapSize(A):
    return len(A) - 1 

def MaxHeapify(A, i): 
    l = left(i)
    r = right(i)
    if l <= HeapSize(A) and A[l] > A[i]:
            largest = l       # always keep 4 white space (or tab) as indent in Python, don't mix up
    else:
            largest = i 
    if r <= HeapSize(A) and A[r] > A[largest]:
            largest = r 
    if largest != i:
            A[i], A[largest] = A[largest], A[i]
            MaxHeapify(A, largest)

def BuildMaxHeap(A):
    for i in range(HeapSize(A) // 2, 0, -1):     # the last non-leaf element is (HeapSize(A)-1) // 2
            MaxHeapify(A, i)

def HeapSort(A):
    BuildMaxHeap(A)
    for i in range(HeapSize(A), 1, -1):   # e.g. range(3,1,-1) gives you [3,2], you miss the 1st element
            A[i], A[1] = A[1], A[i]     # swap with A[0], unless you don't use the 0th element of array
            MaxHeapify(A, 1)      # here is essential error for the algorithm. Since you're doing in-place sorting, you'd not swap the largest element to end of heap then MaxHeapify the WHOLE ARRAY again. I.e. you have to MaxHeapify the heap EXCLUDING the last element

下面是一个基于您的代码的工作版本：

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

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

def parent(i):     # your 'left' and 'right' function is good practice, keep it
    return (i - 1) // 2

def MaxHeapify(A, heap_size, i): 
    l = left(i)
    r = right(i)
    if l <= heap_size and A[l] > A[i]:
        largest = l 
    else:
        largest = i 
    if r <= heap_size and A[r] > A[largest]:
        largest = r 
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        MaxHeapify(A, heap_size, largest)      # important: don't always sort the whole array (size of heap keeps decreasing in 'HeapSort')

def BuildMaxHeap(A):
    heap_size = len(A) - 1    # index of last element of the heap
    for i in range(parent(heap_size), -1, -1):    # don't miss i=0 iteration
        MaxHeapify(A, heap_size, i)

def HeapSort(A):
    BuildMaxHeap(A)
    heap_size = len(A) - 1
    for i in range(heap_size, 0, -1):    # ends at i=1. You don't swap A[0] with A[0], right?
        A[i], A[0] = A[0], A[i]
        MaxHeapify(A, i-1, 0)     # careful here: MaxHeapify which part of the array

测试输出：

>>> a = [9, 0, 5, 7, 4, 6, 3, 8, 1, 2]
>>> BuildMaxHeap(a)
>>> a
[9, 8, 6, 7, 4, 5, 3, 0, 1, 2]
>>> HeapSort(a)
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]