Сложность времени Python HeapSort

Я написал следующий код для 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)?


python heap heapsort
person Saurabh Verma    schedule 27.03.2017    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Да, я считаю, что вы правы. Чтобы сделать это быстрее, замените такие вещи:

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

с:

self.a.pop()

Функция-член списков pop() удаляет и возвращает последний элемент в списке с постоянной временной сложностью.

list хранятся как непрерывная память, то есть все элементы list сохраняются один за другим. Вот почему вставка элемента в середину list обходится так дорого: Python должен сдвигать все элементы после того места, куда вы вставляете, вниз на один, чтобы освободить место для нового элемента. Однако простое удаление элемента в конце list занимает незначительное время, поскольку Python просто должен стереть этот элемент.

person Anonymous1847    schedule 27.03.2017
comment
Кажется, вы правы. Можете ли вы указать мне источник, где я могу увидеть сложность list.pop() или его внутреннюю работу? - person Saurabh Verma; 27.03.2017
comment
stackoverflow.com/questions/195625/ - person Tim Peters; 27.03.2017