python堆排序实现

Question

我正在尝试用Python实现堆排序算法。 我得到了一个错误：list index out of range，尽管如果索引超出范围，那么这部分代码不应该执行。在

def swaper(child,parent,a):

    temp = a[parent]
    a[parent]=a[child]
    a[child]=temp


def digswap(swap,a):

    '''
    swap here is the position of the former child, which was just swapped with 
    its parent. The concept is to check if the node that now contains the parent value
    has childs. If it has, then we might have to restore the heap property.
    '''

    if (2*swap)<=len(a):
            if a[2*swap]>a[swap]:
                    swaper(2*swap, swap, a)
                    digswap(2*swap,a)
    if (2*swap+1)<=len(a):
            if a[2*swap+1]>a[swap]:
                    swaper(2*swap+1, swap, a)
                    digswap(2*swap+1,a)

我得到“if a[2*swap]>；a[swap]”的“list index out of range value”（列表索引超出范围值）。我不明白为什么，因为如果2*swap>；lean（a），这个部分不应该执行。在

Answer 1

列表为0索引。如果2*swap == len(a)，则a中的最后一个有效索引是2*swap - 1，因此出现错误。在

另外，您不需要swapper函数；您只需编写a[parent], a[child] = a[child], a[parent]。它的效率更高，是一种常见的Python习惯用法。在

Answer 2

数组索引从0开始。这将导致您访问数组的最后一个元素。在

假设你有a = [1,2,3,4]，那么{}是4。这个数组的最后一个元素是a[3]。这意味着从这条线来看：

    if (2*swap)<=len(a):

对于swap，您最多可以获得2的值，这意味着您实际上在做：

^{pr2}$

它是数组末尾的1。在