Python heapify 实现运行时

Question

我正在学习一门关于数据结构和算法的类(class)，我应该在其中实现堆排序算法以在指定的时间范围内运行。下面是两个实现:

def generateSwaps():
size=self._n
    for root in range((size//2)-1,-1,-1):
        root_val = self._data[root]             # save root value
        child = 2*root+1
        while(child<size):
            if child<size-1 and self._data[child]>self._data[child+1]:
                child+=1
            if root_val<=self._data[child]:     # compare against saved root value
                break
            self._data[(child-1)//2]=self._data[child]   # find child's parent's index correctly
            self._swaps.append(((child-1)//2,child))
            child=2*child+1
            # print(child)
        self._data[(child-1)//2]=root_val       # here too, and assign saved root value
    return self._data

这里，self._n 是输入的大小，self._data 是需要形成堆的元素列表。这个实现以更短的运行时间通过了测试(最大迭代耗时 0.32 秒)给定 3 秒的时间限制)。

下面是第二个惨败的代码片段(最大迭代耗时 6 秒)

for i in range(self._n//2 , -1, -1):
      child_index = 0
      if (2*i + 2) == self._n:
        child_index = 2*i + 1
      elif (2*i + 2) < self._n:
        child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2]))
      else:
        child_index = 0

      while self._data[i] > self._data[child_index]:
        b = 0
        print("child is smaller for n = " + str(i))
        print(child_index)
        if child_index == 0:
          break
        else:
          self._swaps.append((i, child_index))
          self._data[i], self._data[child_index] = self._data[child_index], self._data[i]
          if child_index <= n//2:
            i = child_index
          else:
            break
          if (2*i + 2) == self._n:
            child_index = 2*i + 1
          elif(2*i + 2) < self._n:
            child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2]))
          else:
            child_index = 0

        print("hello work")
        self._data[i], self._data[child_index] = self._data[child_index], self._data[i]
        print(self._data)

我想了解的是运行时间差异如此之大的原因。我认为这可能是由于在 while 循环中的每一步都交换了列表项，但是由于 python 中的列表基本上是一个数组，我意识到交换也应该是恒定的时间步长(这是我的假设。请纠正我，如果我一个错误)。

提前致谢

Answer 1

正如 user2357112 和 user2357112 在上面的评论中所建议的，问题出在下面一行中的 .index() 操作。

child_index = self._data.index(min(self._data[(2*i) + 1],self._data[(2*i) + 2]))

在数组中查找元素索引的运行时间为 O(n)，因为它需要遍历数组直到找到值的第一个匹配项。这导致第二个实现中的运行时间过长。在第一个实现中，这已被直接比较所考虑的子项及其相邻子项的值所取代，如下所示。

if child<size-1 and self._data[child]>self._data[child+1]:
   child+=1

由于数组对元素的访问是常量时间的，所以上面的实现是常量时间从而减少了运行时间。