Buggy Heap Сортиране

Както видях, някои корекции на вашите оригинални кодове (проверете коментарите):

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]