patternpythonMinor
Python Heap Implementation
Viewed 0 times
implementationpythonheap
Problem
I made this snippet for reviewing my DS textbook.
Is it okay to write iterative loops in function
Any other suggestions or feedbacks are welcome.
Thanks.
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) 0 and self._data[j] 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())Solution
Your method
As a second point, you should not mix naming conventions. You currently use both
You don't need the line-continuation in here, the line is already shorter than 80 characters:
Some
I would rename your method
isEmpty is not needed at all. First, none of your code uses it. Second, if you were to keep it, you should turn it's logic around and rename it to __bool__, this way, if heap automatically works and is True if the heap is not empty. But third, if no __bool__ method exists, Python already calls len(obj) != 0 to determine an object's truthiness, so it is already supplied by defining __len__.As a second point, you should not mix naming conventions. You currently use both
lower_case and camelCase for your method names. PEP8, Python's official style-guide, recommends using lower_case.You don't need the line-continuation in here, the line is already shorter than 80 characters:
def _swap(self, i, j):
self._data[i], self._data[j] = self._data[j], self._data[i]Some
docstrings describing what your methods do and what they expect as inputs/what they return, would also be really good.I would rename your method
del_min to pop_min, because it returns the removed element and not just deletes it.Code Snippets
def _swap(self, i, j):
self._data[i], self._data[j] = self._data[j], self._data[i]Context
StackExchange Code Review Q#157719, answer score: 8
Revisions (0)
No revisions yet.