Python Assignment Solution on Objects and Algorithms - Lab 4 Heap

• 5th Aug, 2022
• 15:57 PM

class Heap:

  size = 0
  arr = []
  capacity = 100

  def __init__(self):    # Default constructor
    self.size = 0
    self.arr = [0]*self.capacity
  
  def show(self):
    s = ""
    for i in range(self.size):
      s +=str(self.arr[i])+" "
    s +="\n\n"
    return s

  def min_heapify(self,i):
    l = self.left(i)
    r = self.right(i)
    smallest = i 
    if (l < self.size and self.arr[l] < self.arr[i]): 
      smallest = l 
    if (r < self.size and self.arr[r] < self.arr[smallest]): 
      smallest = r
    if (smallest != i): 
      temp = self.arr[i]
      self.arr[i] = self.arr[smallest]
      self.arr[smallest] = temp
      self.min_heapify(smallest)

  def insert(self,ele):
    # print("Insert "+str(ele))
    self.size +=1 
    i = self.size - 1; 
    self.arr[i] = ele
    # print("Heap after insert "+str(ele))
  
    while (i != 0 and self.arr[self.parent(i)] > self.arr[i]):
      temp = self.arr[i]
      self.arr[i] = self.arr[self.parent(i)]
      self.arr[self.parent(i)] = temp
      i = self.parent(i)  
    

  def deleteMin(self):
    
    if(self.size==0):
      return 
    elif(self.size==1): 
      self.size -= 1
      return self.arr[0]
    else:
      root = self.arr[0]; 
      self.arr[0] = self.arr[self.size-1] 
      self.size-=1
      self.min_heapify(0)
      return root

  def empty(self):
    return self.size == 0
    
  def getElement(self,index):
    return self.arr[index]
  
  def size(self):
    return self.size

  def parent(self,i):
    return (i-1)//2

  def left(self,i):
    return 2*i
  
  def right(self,i):
    return (2*i)+1

def main():

  input_files = ["in1.txt","in2.txt","in3.txt","in4.txt"]
  output_files = ["out1.txt","out2.txt","out3.txt","out4.txt"]

  i = 0 # Loop variable
  for filename in input_files: 
    f = open(filename, "r")
    line = f.readline()
    ele_list = line.split(" ")

    h = Heap()
    write_string = "Heap\n"

    for ele in ele_list:
      print("i = ",i,"ele = ",ele)
      h.insert(int(ele))
    write_string += h.show()

    # Insert 31
    f = open(output_files[i], "w")
    write_string +="Insert 31\n"
    write_string +="Heap after insert 31\n"
    h.insert(31)
    write_string += h.show()

    # Insert 14
    write_string +="Insert 14\n"
    write_string +="Heap after insert 14\n"
    h.insert(14)
    write_string += h.show()

    while(not h.empty()):  # As long as the heap is not empty
      write_string +="Delete min\n"
      write_string +="Heap after Delete min\n"
      h.deleteMin()
      write_string += h.show()

    write_string +="Deleted all\n"

    i += 1
    f.write(write_string)
    f.close()

main()