Friday 11 December 2015

Max Heap in Python

Q:- Write a menu driven ,python program to implement a Max Heap.


Code for Max Heap


class heap:
    data=list()
    def __init__(self):
        self.data.append(0)
        i=int(input("enter the number of elements to be inserted in the heap"))
        for y in range(1,i+1):
            print "enter element no",y
            self.insert(int(input()))
        print "The created heap is as follows"
        self.display()
    def insert(self,nos):
        self.data.append(nos)
        self.data[0]+=1
        self.upadjust(self.data[0])
    def upadjust(self,l):
        temp=self.data[l]
        while l>1 and temp>self.data[l/2]:
            self.data[l]=self.data[l/2]
            l=l/2
        self.data[l]=temp
    def remove(self):
        if self.data[0]==0:
            print "There are no elements to remove. The heap is empty"
            return
        print "removing the number\t",self.data[1]
        self.data[1]=self.data[self.data[0]]
        self.data[0]-=1
        self.downadjust(1)
    def downadjust(self,i):
        #print "this is the down adjust function"
        while True:
            j=2*i
            if j>self.data[0]:
                break
            if j+1<=self.data[0] and self.data[j+1]>self.data[j]:
                j=j+1
            if self.data[i]>=self.data[j]:
                break
            self.data[j],self.data[i]=self.data[i],self.data[j]
            i=j
           
           
       
    def display(self):
        #print self.data
        if self.data[0]==0:
            print "the heap is empty"
            return
        for i in range(1,self.data[0]+1):
            print self.data[i],"\t",
        print "\n"
#print "This is the test for the main function"
a=heap()
while True:
    print "Menu\n 1.insert\t 2.delete\t 3.display\t 4.exit"
    ch=int(input("Enter ur choice"))
    if ch==4:
        print "Program terminated"
        break
    elif ch==3:
        a.display()
    elif ch==2:
        a.remove()
    elif ch==1:
        a.insert(int(input("Enter the number to be added")))
    else:
        print "Invalid choice entered"
       

No comments:

Post a Comment