Heap sort implementation in Python 3

Question

This code relies on Python3.7.4

I'm learning Heapsort in python 3. Please show me the errors in my code. Runs on my computer but tell me if Python rules or not.

class Heap:
    '''constructor'''
    def __init__(self,lis):
        self.lis=lis
        self.a=[]
    def heapify(self,i):
        self.r=(i-1)//2 #To get the root node
        '''To swap value'''
        if self.lis[i]<self.lis[self.r]:
            self.lis[i],self.lis[self.r]=self.lis[self.r],self.lis[i] 
    def heapSort(self):
        # Build a minheap.
        for j in range(len(self.lis)):
            for i in range(len(self.lis)-1,-1,-1):
                if i==0:
                    self.a.append(self.lis[0])
                    self.lis.remove(self.lis[0])
                else:        
                    self.heapify(i)
        else:
            return self.a

    obj=Heap([5,4,3,2,1])
    print(obj.heapSort())

Answer 1

Style

I suggest you check PEP0008 https://www.python.org/dev/peps/pep-0008/ the official Python style guide when you write your code and Flake8 for style enforcement. The following goes accordingly:

• Blank lines: Surround top-level function and class definitions with two blank lines. Method definitions inside a class are surrounded by a single blank line. Extra blank lines may be used (sparingly) to separate groups of related functions. Blank lines may be omitted between a bunch of related one-liners (e.g. a set of dummy implementations). No blank lines are left between your function definitions.

• Docstrings: Python Docstring is the documentation string which is string literal, and it occurs in the class, module, function or method definition, and it is written as a first statement. Docstrings are accessible from the doc attribute for any of the Python object and also with the built-in help() function can come in handy. Whenever someone using your code is running help(Heap) this will print 'Constructor' which is invalid to what the help function is made for, you should include a description to the class. I suggest you run help(list) might give you some insights on how docstrings might look like. And none of your methods contain docstrings while they should.

  def heapSort(self):
      # Build a minheap.
  

  instead of writing a comment, use a docstring:

  def heap_sort(self):
      """Build a min heap."""
  

• Space around binary operators: a space should be left on both sides of an operator (+-/*&^**//==!=) self.lis=lis should be self.lis = lis self.a=[] should be self.a = [] if i==0: should be if i == 0: ...

• Descriptive variable names: self.lis=lis what is lis? if you're referring to list the common convention is when an identifier conflicts with a built-in function/type it should be written with a trailing underscore: list_ self.a=[] what is a a name should reflect the object it represents. self.r=(i-1)//2 what is r? what is i? ...
• Variable names: method names should be lower_case_with_underscores as well as variable names. def heapSort(self): should be def heap_sort(self):
• Comments: '''To swap value''' in heapify() second line should be replaced with an inline comment # To swap value

Code

• def __init__(self,lis): a class with a single parameter is not a good class, only functions that pass stuff are sufficient.
• self.r=(i-1)//2 instance attribute defined outside the constructor in heapify() method.

• main guard: Use if __name__ == '__main__': guard at the end of your script which allows your module to be imported without running the whole script.

  obj=Heap(xyz)
  print(obj.heapSort())
  

  should be written:

  if __name__ == '__main__':
      obj = Heap(xyz)
      print(obj.heapSort())
  

Answer 2

Most of what I say here is covered in PEP8.

• In assignment statements, surround an "=" with a space on either side.
• Function parameters are separated by a comma followed by another space
• If '''To swap value''' is a docstring, it needs up one line.
• Comparison operators like "<" also need a space on either side.
• Use variables with meaningful names. a, lis, j, and i are not meaningful.
• Comma seperation in tuple assignment should also have a space after each comma.
• if i==0: can be replaced with if not i:

I myself lack experience with sorts and time-complexity, so I'll leave that to others.

Answer 3

Code after the suggestion

class Heap:
    def __init__(self,List):
        self.List = List
        self.a = []
    def heapify(self,i):
        #To swap variable
        # (i-1) // 2 = is get the root node
        if self.List[i] < self.List[(i-1) // 2]:
                self.List[i] , self.List[(i-1) // 2] = self.List[(i-1) // 2] , self.List[i] 
    def heapSort(self):
        # Build a minheap.
        for i in range(len(self.List)-1,-1,-1):
            if not i:
                self.a.append(self.List[0])
                self.List.remove(self.List[0])
            else:        
                self.heapify(i)
        else:
            if self.List:
                self.heapSort()
        return self.a

if __name__=="__main__":
    obj=Heap([5,4,3,2,1])
    print(obj.heapSort())