#heap

#This is a max heap

class heap():

def __init__(self):

self.heapArray = []

def displayHeapArray(self):

print self.heapArray

def getLeftChildIndex(self, root):

return (2*root)+1

def getRightChildIndex(self, root):

return (2*root)+2

def getParentIndex(self, child):

if(child%2 == 1):

#Left child

return (child-1)/2

return (child-2)/2

def bottomHeapify(self, childIndex):

if(childIndex != 0):

#Get parent index

parentIndex = self.getParentIndex(childIndex)

#Check if the parent is small

if(self.heapArray[parentIndex] < self.heapArray[childIndex]):

#Swap parent and child

self.heapArray[parentIndex], self.heapArray[childIndex] = self.heapArray[childIndex], self.heapArray[parentIndex]

self.bottomHeapify(parentIndex)

def add(self, data):

self.heapArray.append(data)

self.bottomHeapify(len(self.heapArray)-1)

self.displayHeapArray()

def topHeapify(self, parentIndex):

if(parentIndex < len(self.heapArray)):

#Find childern

rChild = self.getRightChildIndex(parentIndex)

lChild = self.getLeftChildIndex(parentIndex)

#If the childern are in bound

if(rChild < len(self.heapArray) and lChild < len(self.heapArray)):

#Find bigger child

if(self.heapArray[rChild] > self.heapArray[lChild]):

#Swap with r child

self.heapArray[rChild], self.heapArray[parentIndex] = self.heapArray[parentIndex], self.heapArray[rChild]

self.topHeapify(rChild)

else:

#Swap with l child

self.heapArray[lChild], self.heapArray[parentIndex] = self.heapArray[parentIndex], self.heapArray[lChild]

self.topHeapify(lChild)

def remove(self):

if not self.heapArray:

print "Heap is empty"

return

print "Removed element "+str(self.heapArray[0])

self.heapArray[0] = self.heapArray[-1]

del self.heapArray[-1]

self.topHeapify(0)

self.displayHeapArray()

#Main Program

h = heap()

h.add(5)

h.add(6)

h.add(7)

h.remove()

h.add(8)

h.remove()

h.remove()

h.remove()

h.remove()