Sunday, October 27, 2013

Heap Sort in Python

class heap1:
    num=0;
    arr=list();
    heap=list();
   
    def input_arr(self):
        self.arr=list();
        self.num=int(raw_input("Enter the total Numbers:"))
        self.arr.append(self.num)
        for i in xrange(self.num):
            n=int(raw_input("Num:"))
            self.arr.append(n)
        return
   
    def create(self):
        self.heap=list()
        self.heap=self.arr[:]
        self.heap[0]=0
        for i in xrange(1,self.num+1,1):
            self.insert(self.arr[i])
        return
   
    def insert(self,i):
        n=self.heap[0]
        self.heap[n:n]=[self.heap[n],i]
        n=n+1
        self.heap[0]=n
        self.upadjust(n)
        return
   
    def upadjust(self,i):
        while (self.heap[i]>self.heap[i/2] and i>1):
            temp=self.heap[i]
            self.heap[i]=self.heap[i/2]
            self.heap[i/2]=temp
            i=i/2
        return
   
    def downadjust(self,i):
        flag=1
        while((2*i<=self.num) and flag==1):
            j=2*i
            if((j+1<=self.num) and (self.heap[j+1]>self.heap[j])):
                j=j+1
            if(self.heap[i]>self.heap[j]):
                flag=0
            else:
                temp=self.heap[j]
                self.heap[j]=self.heap[i]
                self.heap[i]=temp
                i=j
        return
   
    def delete(self):
        x=self.heap[1]
        n=self.heap[0]
        self.heap[1]=self.heap[n]
        n=n-1
        self.heap[0]=n
        self.downadjust(1)
        return x
   
    def display(self):
        n=self.heap[0]
        for i in xrange(1,n+1,1):
            print self.heap[i]
        return
   
obj=heap1()
a=1
while a==1:
    print "1.Input an Array"
    print "2.Insert an element"
    print "3.Create Heap from array"
    print "4.Delete the Maximum Element"
    print "5.Display"
    print "6.Exit"
    b=int(raw_input("Enter an Option:"))
    if(b==1):
        obj.input_arr()
    elif(b==2):
        i=int(raw_input("Enter the Element:"))
        obj.insert(i)
    elif(b==3):
        obj.create()
        obj.display()
    elif(b==4):
        j=obj.delete()
        print "Tne Maximum element deleted is "+str(j)
        obj.display()
    elif(b==5):
        obj.display()
    elif(b==6):
        a=0

No comments:

Post a Comment

Perform a suitable assignment using Xen Hypervisor or equivalent open source to configure it. Give necessary GUI.

 To install kvm on Fedora:  yum install kvm  yum install virt-manager libvirt libvirt-python python-virtinst  su -c "yum install @v...