Python HeapSort Time Complexity

Question

I've written the following code for HeapSort, which is working fine:

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()

However, it seems that the function heapSort here will take time O(n^2), due to list slicing. (For a list of size 'n', slicing it to 'n-1' will take O(n-1) time). Can anyone confirm if my thinking is correct over here ? If yes, what should be the minimal change in heapSort function to make it run in O(nlogn) ?

Anonymous1847 · Accepted Answer · 2017-03-27T04:07:07.560

4

Yes, I believe you are correct. To make it faster, replace things like this:

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

with:

self.a.pop()

The pop() member function of lists removes and returns the last element in the list, with constant time complexity.

lists are stored as contiguous memory, meaning all the elements of a list are stored one after the other. This is why inserting an element in the middle of a list is so expensive: Python has to shift all the elements after the place you're inserting in down by one, to make space for the new element. However, to simply delete the element at the end of list takes negligible time, as Python merely has to erase that element.

edited Mar 27 '17 at 04:07

answered Mar 27 '17 at 03:26

Anonymous1847

2,568
10
16

It seems you are correct. Can you point me to a source where I can see list.pop() complexity or its internal working ? – Saurabh Verma Mar 27 '17 at 03:31
1

http://stackoverflow.com/questions/195625/what-is-the-time-complexity-of-popping-elements-from-list-in-python – Tim Peters Mar 27 '17 at 03:37

Python HeapSort Time Complexity

1 Answers1