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())
up vote 8 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.