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:

Expected output:

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!

What do you expect to be the result of heaptype=heaptype.title()? This instruction alters the value of heaptype provided as a variable to the function. — itprorh66
– itprorh66, Commented Dec 20, 2021 at 15:15
@itprorh66 Sir,the idea was that user can enter heaptype regardless of it's case(bcz sir the condition of heaptype inside function is writteen in title case) — Super Ultra Noob
– Super Ultra Noob, Commented Dec 20, 2021 at 15:16

trincot · Accepted Answer · 2021-12-20 17:02:12Z

2

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.

answered Dec 20, 2021 at 17:02

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Super Ultra Noob Over a year ago

Thank you soo much sir for again helping me out :)

Collectives™ on Stack Overflow

my custom heapify method not working properly in python

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related