Implementing heap in Python

This is basically a straightforward heap implementation. I am just moving from C to Python and I wanted to make sure that I follow Python's best practices in general. This heap is supposed to support data from any data type with any comparing function.

```
class Heap(object):
""""
Attributes:
heap: List representation of the heap
compar(p, c): comparator function, returns true if the relation between p and c is parent-chield
"""
def __init__(self, compar):
self.heap = []
self.compar = compar
def is_empty(self):
return len(self.heap) == 0
def _inv_heapify(self, element_id):
"""
Do heapifying starting from bottom till it reaches the root.
"""
while element_id > 0:
if self.compar(self.heap[element_id / 2], self.heap[element_id]):
return
self.heap[element_id / 2], self.heap[element_id] = self.heap[element_id], self.heap[element_id / 2]
element_id /=2
def _heapify(self, element_id):
"""
Do heepifying starting from the root.
"""
l = len(self.heap)
if l == 1:
return
while 2 * element_id < l:
el_id = 2 * element_id
if 2 element_id + 1 < l and self.compar(self.heap[element_id 2 + 1], self.heap[element_id * 2]):
el_id += 1
if self.compar(self.heap[element_id], self.heap[el_id]):
return
self.heap[element_id], self.heap[el_id] = self.heap[el_id], self.heap[element_id]
element_id = el_id
def del_min(self):
if self.is_empty():
return None
x = self.heap.pop(0)
if not self.is_empty():
self.heap = [self.heap[-1]] + self.heap[0:-1]
self._heapify (0)
return x
def min(self):
if self.is_empty():
return None
return self.heap[0]
def add(self, element):
self.heap +=[elemen

You have a couple of PEP8 style problems:

• Functions should have an empty line above and below them.

• Function calls should have their bracket immediately after the name. So fn( not fn (.

• Assignment operators should have a space either side of them.

• Try to keep code less than 80 characters long.

You also have a couple of naming problems:

• compar should be compare or comparer, since compar is not a word. If you wanted to shorten it comp would be the best shortened version, but is worse than both the written out versions.

• Lists and arrays don't have IDs, they have indexes. And so element_id is confusing. At first I used item_index or element_index, but decided to instead use parent and child to better describe the parent child relationship.

• In heapify I'd change el_id to child and element_id to parent. (And you should use child rather than parent * 2)

• For better readability, and for a minor performance boost, I used heap = self.heap.

Other things I'd change:

• Your constructor shouldn't need to be passed compare, and so it could default to operator.lt. You may also want to take a heap as input, but you may need to add more code so it works correctly.

• Add a __repr__, so that you can more easily tell what the object is.

• In del_min when you add the two lists, it runs in \$O(n)\$ time. Where you can do the same with heap.pop(), which runs in \$O(1)\$ time.

• You may want to look at heapq's source code to find other things you can do. It for example uses; _siftup, and _siftdown, and; _siftup_max, and _siftdown_max. Where you only write two of these.

Combining the above together gets you:

import operator

class Heap(object):
    """"
    Attributes:
        heap: List representation of the heap
        compare(p, c): comparator function, returns true if the relation between p and c is parent-chield
    """
    def __init__(self, heap=None, compare=operator.lt):
        self.heap = [] if heap is None else heap
        self.compare = compare

    def __repr__(self):
        return 'Heap({!r}, {!r})'.format(self.heap, self.compare)

    def _inv_heapify(self, child_index):
        """
        Do heapifying starting from bottom till it reaches the root.
        """
        heap, compare = self.heap, self.compare
        child = child_index
        while child > 0:
            parent = child // 2
            if compare(heap[parent], heap[child]):
                return
            heap[parent], heap[child] = heap[child], heap[parent]
            child = parent

    def _heapify(self, parent_index):
        """
        Do heepifying starting from the root.
        """
        heap, compare = self.heap, self.compare
        length = len(heap)
        if length == 1:
            return
        parent = parent_index
        while 2 * parent < length:
            child = 2 * parent
            if child + 1 < length and compare(heap[child + 1], heap[child]):
                child += 1
            if compare(heap[parent], heap[child]):
                return
            heap[parent], heap[child] = heap[child], heap[parent]
            parent = child

    def del_min(self):
        heap = self.heap
        last_element = heap.pop()
        if not heap:
            return last_element
        item = heap[0]
        heap[0] = last_element
        self._heapify(0)
        return item

    def min(self):
        if not self.heap:
            return None
        return self.heap[0]

    def add(self, element):
        self.heap.append(element)
        self._inv_heapify(len(self.heap) - 1)

Rather than implementing this yourself, you can use Pythons heapq, which may be written in C.
Since it's not a class you can easily make it one by wrapping it in one. But it doesn't have your custom comparisons, it is instead always a min heap.
If you need the custom comparisons, you could instead look into writing your own comparison object that does what you want, and use the heap class.

class Heap(list):
    def __init__(self, heap=None):
        if heap is None:
            heap = []
        heapq.heapify(heap)
        super(Heap, self).__init__(heap)

    def __repr__(self):
        return 'Heap({})'.format(super(Heap, self).__repr__())

    def push(self, item):
        return heapq.heappush(self, item)

    def heappop(self):
        return heapq.heappop(self)

    def pushpop(self, item):
        return heapq.heappushpop(self, item)

    def replace(self, item):
        return heapq.heapreplace(self, item)

    def nlargest(self, n, *args, **kwargs):
        return heapq.nlargest(n, self, *args, **kwargs)

    def nsmallest(self, n, *args, **kwargs):
        return heapq.nsmallest(n, self, *args, **kwargs)

StackExchange Code Review Q#156027, answer score: 14