HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Python Heap Implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationpythonheap

Problem

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)  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 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.