堆排序实现几乎只对数组进行排序

Question

我一直在尝试用Ruby实现堆排序，但到目前为止，我的算法只对90%的数组进行了正确的排序，而不是其余的。有人能看到哪里出了问题吗？

这是我的代码

require 'pp'

def left(i)
    (i+1)*2-1
end

def right(i)
    (i+1)*2
end

def max_heapify(a, root)
    left, right = left(root), right(root)
    max = root
    if left < a.length and a[left] > a[max]
        max = left
    end
    if right < a.length and a[right] > a[max]
        max = right
    end
    if max != root
        a[root], a[max] = a[max], a[root]
        max_heapify(a, max)
    else
        a
    end
end

def build_max_heap(a)
    ((a.size-1)/2).downto(0) do |i|
        max_heapify(a, i)
    end
    a
end

def heap_sort(a)
    len = a.size
    build_max_heap(a)
    (len-1).downto(0) do |i|
        a[0], a[i] = a[i], a[0]
        a.delete_at(len)
        max_heapify(a, 0)
    end 
    a
end

a = (1..10).to_a.shuffle
pp heap_sort(a)

结果：[10, 9, 7, 8, 6, 2, 4, 5, 1, 3]

Answer 1

在排序过程中，当您将max元素移动到末尾时，不要再接触它，它将被排序，并且要排序的数组(和堆)应该在它之前结束。

您还需要向max_heapify添加一个参数，以告知堆的结束位置，它不是数组的结束位置。

require 'pp'

def left(i)
    i*2+1
end

def right(i)
    i*2+2
end

def max_heapify(a, root, len)
    left, right = left(root), right(root)
    max = root
    if left < len and a[left] > a[max]
        max = left
    end
    if right < len and a[right] > a[max]
        max = right
    end
    if max != root
        a[root], a[max] = a[max], a[root]
        max_heapify(a, max, len)
    else
        a
    end
end

def build_max_heap(a)
    ((a.size-1)/2).downto(0) do |i|
        max_heapify(a, i, a.length)
    end
    a
end

def heap_sort(a)
    len = a.size
    build_max_heap(a)
    (len-1).downto(0) do |i|
        a[0], a[i] = a[i], a[0]
        max_heapify(a, 0, i)
    end
    a
end

a = (1..10).to_a.shuffle
pp heap_sort(a)

PP。不确定delete_at是做什么的(不知道Ruby)，但我强烈怀疑它是不需要的，在排序过程中，你没有从数组中“删除”任何东西，你只是重新排列元素。