class HeapArray:
def __init__(self):
self._data = []
self._size = 0
def __str__(self):
return ' '.join([str(i) for i in self._data]) + " Size = "+str(self._size) #try to understand what??
def is_empty(self):
return self._size == 0
def insert(self,e):
self._data.append(e)
# Now we need to adjust
index = self._size
while index > 0 and self._data[index] < self._data[(index-1)//2]:
temp = self._data[index]
self._data[index] = self._data[(index-1)//2]
self._data[(index-1)//2] = temp
index = (index - 1)//2
self._size = self._size + 1
return True
def delete_min(self):
if self._size == 0: #empty heap
return None
elif self._size == 1: # one element heap
min = self._data.pop(0)
self._size = self._size - 1
return min
else: # more than one element heap
min = self._data[0]
self._data[0] = self._data.pop(self._size-1)
self._size = self._size - 1
index = 0
while 2*index+1 < self._size-1: #while there is at least one child continue adjustments
if 2*index+2 < self._size-1: # 2 children
if self._data[2*index+1] > self._data[2*index+2]: # first child bigger than second child
if self._data[index] < self._data[2*index+2]:
break
else: # exchange with second child 2*index+2
temp = self._data[index]
self._data[index] = self._data[2*index+2]
self._data[2*index+2] = temp
index = 2*index+2
else: # first child smaller than second child
if self._data[index] < self._data[2*index+1]: # parent smaller than both children
break
else: # exchange with first child 2*index+1
temp = self._data[index]
self._data[index] = self._data[2*index+1]
self._data[2*index+1] = temp
index = 2*index+1
else: # one child
if self._data[index] > self._data[2*index+1]: # exchange or swap
temp = self._data[index]
self._data[index] = self._data[2*index+1]
self._data[2*index+1] = temp
index = 2*index+1
else:
break
return min