my custom heapify method not working properly in python

Question

I am learning data structures and my code is not working properly..I tried dubugging and couldn't found anything(seems like heapifyinsert() is not doing anything)

Here is my code:

class Heap:
    def __init__(self,size):
        self.heap=[None]*(size+1)
        self.heapsize=0
        self.maxheapsize=size+1


    def levelordertransversal(self):
        if not self.heap:
            raise Exception('Heap doesn\'t exists')
        for x in range(1,self.heapsize+1):
            print(self.heap[x])

    def heapifyinsert(self,index,heaptype):
        heaptype=heaptype.title()
        parentindex=int(index/2)
        if parentindex<=1:
            return
        if heaptype=='Min':
            if self.heap[index]<self.heap[parentindex]:
                temp=self.heap[index]
                self.heap[index]=self.heap[parentindex]
                self.heap[parentindex]=temp
            self.heapifyinsert(parentindex,heaptype)
        elif heaptype=='Max':
            if self.heap[index]>self.heap[parentindex]:
                temp=self.heap[index]
                self.heap[index]=self.heap[parentindex]
                self.heap[parentindex]=temp
            self.heapifyinsert(parentindex,heaptype)

    def insertnode(self,nodevalue,heaptype):
        if self.heapsize+1==self.maxheapsize:
            raise Exception('Heap is full!!')
        self.heap[self.heapsize+1]=nodevalue
        self.heapsize+=1
        self.heapifyinsert(self.heapsize,heaptype)

h=Heap(5)
h.insertnode(4,'Max')
h.insertnode(5,'Max')
h.insertnode(2,'Max')
h.insertnode(1,'Max')
h.levelordertransversal()

Current output:

4
5
2
1

Expected output:

5
4
2
1

So here in the above code I tried to implement heap starting with index position 1(for the sake of simplicity) and in heapifyinsert() method we are taking parentindex and checking if the value at parent index is greater or less according to heap type and swapping the values

Any help or clue will be appreciated..Thanks!

Answer 1

The problem is that the recursion stops too soon. 1 is a valid index in your heap, while 0 is not, so that means you need to change:

if parentindex<=1:

...to:

if parentindex< 1:

This will fix the issue.

Some other comments on your code:

• The recursion can stop when the comparison between child and parent is OK. So move the call of self.heapifyinsert(parentindex,heaptype) inside the preceding if block.

• The heaptype parameter should not be defined for the insertnode, because obviously it makes no sense to provide a different value for a next call of insertnode: either it should always be "Min" or always be "Max". So this should be a parameter for the constructor and be stored as an attribute of the heap

• In Python you can easily swap values using tuple assignment, without the need of a temp variable

• int(index/2) will first perform a float division and the convert it back to integer. It makes more sense to just use integer division: index // 2

• if not self.heap: is unnecessary: as the heap attribute is initialised by the constructor, this should never happen

• Avoid some code repetition: the swap and the recursive call is the same independent on the heap type, so try to rearrange your code so to only have this coded once.