Python HeapSort 时间复杂度

Question

我为 HeapSort 编写了以下代码，它运行良好：

class Heap(object):
        def __init__(self, a):
            self.a = a

        def heapify(self, pos):
            left = 2*pos + 1
            right = 2*pos + 2
            maximum = pos

            if left < len(self.a) and self.a[left] > self.a[maximum]:
                maximum = left
            if right < len(self.a) and self.a[right] > self.a[maximum]:
                maximum = right

            if maximum != pos:
                self.a[pos], self.a[maximum] = self.a[maximum], self.a[pos]
                self.heapify(maximum)

        def buildHeap(self):
            for i in range(len(self.a)/2, -1, -1):
                self.heapify(i)

        def heapSort(self):
            elements = len(self.a)
            for i in range(elements):
                print self.a[0]
                self.a[0] = self.a[-1]
                self.a = self.a[:-1]
                self.heapify(0)

        def printHeap(self):
            print self.a

if __name__ == '__main__':
    h = Heap(range(10))
    h.buildHeap()
    h.printHeap()
    h.heapSort()

但是，由于列表切片，这里的函数heapSort似乎需要时间O(n^2)。（对于大小为 'n' 的列表，将其切片为 'n-1' 将花费 O(n-1) 时间）。谁能确认我的想法在这里是否正确？如果是，heapSort 函数中的最小变化应该是什么，以使其在 O(nlogn) 中成为运行？

Answer 1

是的，我相信你是对的。为了让它更快，替换这样的东西：

self.a = self.a[:-1]

与：

self.a.pop()

列表的 pop() 成员函数移除并 returns 列表中的最后一个元素，具有恒定的时间复杂度。

list 存储为连续内存，这意味着 list 的所有元素都一个接一个地存储。这就是为什么在 list 中间插入一个元素如此昂贵：Python 必须将您插入的位置之后的所有元素向下移动一个，以使 space对于新元素。但是，简单地删除 list 末尾的元素所花费的时间可以忽略不计，因为 Python 只需删除该元素即可。

Python HeapSort 时间复杂度

Python HeapSort Time Complexity

python

heap

heapsort