Min Heap : Array Implementation

MinHeap_Array.py

#-----------------------------------------------------------------
#-------------------------Min Heap--------------------------------
#-----------------------------------------------------------------

# Min Heap class
class MinHeap:
    def __init__ (self, array):
        self.heap = self.bulidHeap(array)

    # This method take an array and build a heap from it
    def bulidHeap(self,array):
        n = len(array)
        index = n//2 -1
        for i in range(index,-1,-1):
            self.heapify_down(array,n,i)
        #print (array)
        return array
    
    # This method takes an array, length of array and an index as parameter
    # This is a helper method to buildHeap and changeValue method
    # It follows Top-Down approch
    def heapify_down(self,array,n,index):
        minimum = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < n and array[left] < array[minimum]:
            minimum = left

        if right < n and array[right] < array[minimum]:
            minimum = right

        if minimum != index:
            self.swap(index,minimum,array)
            self.heapify_down(array,n,minimum)

    # This method takes an array and an index as a parameter
    # This is a helper method to changeValue and insert method
    # It follows Bottom-Up approch
    def heapify_up(self,heap,index):
        parent = (index - 1)//2
        if index > 0 and heap[parent] > heap[index]:
            self.swap(parent,index,self.heap)
            self.heapify_up(self.heap,parent)

    # This method deletes given key from the heap
    def remove(self,value):
        index = self.check(value)
        if index == -1:
            return "No such element found !!"
        self.swap(index,len(self.heap)-1,self.heap)
        self.heap.pop()
        self.heapify_down(self.heap,len(self.heap),index)
        return "Done"

    # This method changes the given key to specified value
    def changeValue(self,new,old):
        index = self.check(old)
        if index == -1:
            return "No such element found. !!"
        self.heap[index] = new
        parent = (index - 1)//2
        #print(index,parent)
        if new < self.heap[parent] :
            self.heapify_up(self.heap,index)
        else:
            self.heapify_down(self.heap,len(self.heap),index)
        return "Done"

    # This method check whether the given element is there in the heap or not
    # This is just a helper method 
    def check(self,value):
        index = -1
        for i in range(len(self.heap)):
            if value == self.heap[i]:
                index = i
        return index

    # This method check whether heap is empty or not
    def isEmpty(self):
        if self.heap:
            return True
        return False

    # This method returns the minimum value
    def getMin(self):
        if not self.isEmpty():
            return "Heap Empty"
        return self.heap[0]

    # this method just swap two values.
    # this is just a helper method
    def swap(self,i,n, heap):
        heap[i],heap[n] = heap[n],heap[i]

    # This method return and delete the minimum key
    def extractMin(self):
        if not self.isEmpty():
            return "Heap Empty"
        self.swap(0,len(self.heap)-1,self.heap)
        value = self.heap.pop()
        self.heapify_down(self.heap,len(self.heap),0)
        return value

    # this method insert new key into the heap 
    def insert(self,value):
        self.heap.append(value)
        self.heapify_up(self.heap,len(self.heap)-1)


# Testing
if __name__ == "__main__":

    print("Creating object of MinHeap class")
    heap = MinHeap([5,1,2,8,9,4,7,6])
    print("Getting Minimum key : ",heap.getMin())
    print("Extracting Minmum key : " , heap.extractMin())
    print("Getting Minimum Key : " , heap.getMin())
    value = 0
    print("Inserting : ",value)
    heap.insert(0)
    print("Getting Minimum Key : " , heap.getMin())
    remove = 6
    print("Removing : ", remove)
    print("Remove status : " , heap.remove(remove))
    new = 10
    old = 5
    print("Changing ", old, " To ", new)
    print("Change Status : ", heap.changeValue(new,old))

    
    for i in range(8):
        print(heap.extractMin())