Buggy Heap Sort

Question

Below is my attempt at Heap Sort which is suppose to resemble what is shown in CLRS from page 152 and onward.

If I pass A = [9, 0, 5, 7, 4, 6, 3, 8, 1, 2] as input. The output of BuildMaxHeap is [9, 8, 6, 7, 4, 5, 3, 0, 1, 2]. Which seems right. However passing the same input to HeapSort gives me [9, 8, 4, 7, 2, 3, 5, 6, 1, 0] which is defiantly wrong.

Can anyone shred some light on what I'm doing wrong?

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

As I saw, some corrections on your original codes (check the comments):

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

Then below is a working version that based on your codes:

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

Output of test:

>>> 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]