I made this snippet for reviewing my DS textbook.
Is it okay to write iterative loops in function _upheap and _downheap?
Any other suggestions or feedbacks are welcome.
Thanks.
# heap.py
# by kidkkr
# Mar-14-2017, 07:29PM
class Heap:
__slots__ = '_data'
def __init__(self):
self._data = []
def __len__(self):
return len(self._data)
def isEmpty(self):
return len(self) == 0
def add(self, item):
self._data.append(item)
self._upheap(len(self) - 1)
def del_min(self):
self._swap(0, len(self) - 1)
res = self._data.pop()
self._downheap(0)
return res
def _left(self, j):
return 2*j + 1
def _hasLeft(self, j):
return self._left(j) < len(self)
def _right(self, j):
return 2*j + 2
def _hasRight(self, j):
return self._right(j) < len(self)
def _parent(self, j):
return (j - 1)/2
def _swap(self, i, j):
self._data[i], self._data[j] = \
self._data[j], self._data[i]
def _upheap(self, j):
while j > 0 and self._data[j] < self._data[self._parent(j)]:
self._swap(j, self._parent(j))
j = self._parent(j)
def _downheap(self, j):
while j < len(self):
if self._hasLeft(j):
smallChild = self._left(j)
if self._hasRight(j) and \
self._data[smallChild] > self._data[self._right(j)]:
smallChild = self._right(j)
if self._data[j] > self._data[smallChild]:
self._swap(j, smallChild)
j = smallChild
else:
break
else:
break
if __name__ == "__main__":
### Test Codes
a = Heap()
a.add(21)
a.add(28)
a.add(16)
a.add(9)
a.add(14)
a.add(21)
a.add(26)
a.add(33)
a.add(22)
a.add(6)
a.add(22)
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
print(a.del_min())
