堆排序（Heapsort）实现问题求助：代码未正确排序

我的堆排序代码未达到预期效果，示例如下：

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

显然结果未正确排序，我参照网上伪代码编写但找不到错误，附上完整代码：

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

错误原因 #

核心问题出在MaxHeapify与heapSort的边界控制逻辑不匹配：

• heapSort中维护了一个递减的n变量，用来标记当前需要调整的堆的有效边界（末尾已排序的元素不应参与堆调整）
• 但MaxHeapify直接用length(h.keys)作为堆的大小，完全忽略了heapSort的边界控制，导致每次调整都会把已排序的末尾元素重新纳入堆结构，破坏排序流程。

修复方案 #

修改MaxHeapify函数，新增heap_size参数指定当前堆的有效范围，同步调整调用逻辑：

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

# 新增heap_size参数，限定堆的有效调整范围
function MaxHeapify(h::MaxHeap, i::Int, heap_size::Int)
    l = left(i)
    r = right(i)
    largest = i
    if l <= heap_size && h.keys[l] > h.keys[i]
        largest = l
    end
    if r <= heap_size && h.keys[r] > h.keys[largest]
        largest = r
    end
    if largest != i
        h.keys[i], h.keys[largest] = h.keys[largest], h.keys[i]
        MaxHeapify(h, largest, heap_size)
    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)
    heap_size = length(h.keys)
    for i = heap_size:-1:2
        h.keys[1], h.keys[i] = h.keys[i], h.keys[1]
        heap_size -= 1
        # 传入当前有效堆大小进行调整
        MaxHeapify(h, 1, heap_size)
    end
end

验证结果 #

运行示例代码：

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

此时得到正确的升序排序结果。若需要降序排序，可调整heapSort的交换逻辑或改用小顶堆实现。

内容的提问来源于stack exchange，提问作者dg_m87