Python heapify 实现 运行 时间

Question

我正在学习一门关于数据结构和算法的课程，我应该在指定的时间范围内将堆排序算法实现到 运行。下面是两个实现：

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是需要组成一个heap.This实现的元素列表，通过测试以低得多的运行 时间（给定的 3 秒时间限制中最大的迭代最多需要 0.32 秒）。

下面是第二个惨败的代码片段（最大迭代耗时 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)

我想弄明白的是运行ning 时间差异如此之大的原因。我认为这可能是由于在 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)，因为它需要遍历数组直到找到 value.This 中的第一个匹配项导致过长 运行第二次实施的时间。在第一个实现中，这已被直接比较所考虑的子项及其相邻子项的值所取代，如下所示。

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

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