CODEWITHSUNDEEP
pythonheapheapsort
Saurabh Verma
Saurabh Verma

Reputation: 6728

Python HeapSort Time Complexity

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

Upvotes: 0

Views: 367

Answers (1)

Anonymous1847
Anonymous1847

Reputation: 2598

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.

Upvotes: 4

Related Questions