How to implement heapsort?

Question

My heapsort-code doesnt do what it should. For example

h = MaxHeap([1,9,5,7,8])
heapSort(h)
h.keys # [9 8 5 7 1]

is obviously not sorted. I just cant find my error. I already tried a lot of things. It is basically the pseudocode I found on the internet so I have no idea what I am doing wrong. Would be really nice if somebody could give me a hint or explain to me how I could improve my code. Thanks in advance!

function left(i)
    return 2*i
end
function right(i)
    return 2*i + 1
end

struct MaxHeap
    keys::Vector{Int}
end

function MaxHeap(keys::Vector{Int})
    h = MaxHeap([])
    for k in keys
        push!(h.keys, k)
    end
    BuildMaxHeap(h)
    return h
end

function MaxHeapify(h::MaxHeap, i::Int)
    n = length(h.keys)
    l = left(i)
    r = right(i)
    if l <= n && h.keys[l] > h.keys[i]
        largest = l
    else
        largest = i
    end
    if r <= n && h.keys[r] > h.keys[largest]
        largest = r
    end
    if largest != i
        # swap A[i] and A[largest]
        h.keys[i], h.keys[largest] = h.keys[largest], h.keys[i]
        MaxHeapify(h, largest)
    end
end

function BuildMaxHeap(h::MaxHeap)
    n = length(h.keys)
    for i = (n ÷ 2):-1:1
        MaxHeapify(h, i)
    end
end

function heapSort(h::MaxHeap)
    BuildMaxHeap(h)
    n = length(h.keys)
    for i = n:-1:2
        h.keys[1], h.keys[i] = h.keys[i], h.keys[1]
        n = n - 1
        MaxHeapify(h, 1)
    end
end

Answer 1

The n = n - 1 update in heapSort currently doesn't do anything. You need to change the code so that this n is used as the new logical size of the heap, so the part of the array that is already sorted doesn't get modified. For example:

function MaxHeapify(h::MaxHeap, i::Int, n)
    l = left(i)
    r = right(i)
    if l <= n && h.keys[l] > h.keys[i]
        largest = l
    else
        largest = i
    end
    if r <= n && h.keys[r] > h.keys[largest]
        largest = r
    end
    if largest != i
        # swap A[i] and A[largest]
        h.keys[i], h.keys[largest] = h.keys[largest], h.keys[i]
        MaxHeapify(h, largest, n)
    end
end

function BuildMaxHeap(h::MaxHeap)
    n = length(h.keys)
    for i = (n ÷ 2):-1:1
        MaxHeapify(h, i, n)
    end
end

function heapSort(h::MaxHeap)
    BuildMaxHeap(h)
    n = length(h.keys)
    for i = n:-1:2
        h.keys[1], h.keys[i] = h.keys[i], h.keys[1]
        n = n - 1
        MaxHeapify(h, 1, n)
    end
end