Implementing heap in Python

Question

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 +=[element]
        self._inv_heapify (len (self.heap) - 1)

Answer 1

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)

Answer 2

Thank you for the great question and the great review @Peilonrayz ! Don't have much to criticize, only a few things which I would personally change. It's my first heap implementation, so please double check my suggestions...

• Getting the parent/child is a bit of magic numbering, maybe put that into a separate function
• Both in heapify/inv_heapify the words child and parent exist. However, if I'm not mistaken, one really focuses on the current node + its children, the other one on the current node + its parents.
• A line such as "child+=1" seems a bit weird to me. "idx_child+=1" seems cleaner
• Are the words heapify / inv_heapify chosen correctly here? Wikipedia states that "heapify: create a heap out of given array of elements". Thus, I would expect an array as function input. Instead, it receives an index...
• While the function name "compare" seems common (e.g. std::string::compare()), I like to name boolean returning functions with a "has" or "is" prefix. In a case of maxheap we could name it "is_bigger_than" (similar to operator.gt = "greater than", but could be custom function)

Putting everything together...:

class Heap:
    def __init__(self):
        self.lst = []
        self.is_bigger_than = operator.gt

    def add(self, x):
        self.lst.append(x)
        idx_node = len(self.lst) - 1
        self._siftup(idx_node)

    def pop(self):
        if len(self.lst) == 0:
            print("Error: Heap empty!")
        else:
            lst = self.lst
            lst[0], lst[-1] = lst[-1], lst[0]  # switch first with last element
            res = lst.pop()  # pop last element
            self._siftdown(0)
            return res

    def _siftup(self, inode):
        lst = self.lst
        iparent = self._get_parent(inode)
        if iparent >= 0 and self.is_bigger_than(lst[inode], lst[iparent]):
            lst[inode], lst[iparent] = lst[iparent], lst[inode]
            self._siftup(iparent)

    def _siftdown(self, inode):
        lst = self.lst
        ichildren = self._get_children(inode)
        for ichild in ichildren:  # do I need to sift down
            if ichild < len(lst) and self.is_bigger_than(lst[ichild], lst[inode]):
                lst[ichild], lst[inode] = lst[inode], lst[ichild]
                self._siftdown(ichild)

    def _get_parent(self, idx_child):
        idx_parent = int((idx_child - 1) / 2)  # zero-based array
        return idx_parent

    def _get_children(self, idx_parent):
        idx_children = 2 * idx_parent + 1, 2 * idx_parent + 2
        return idx_children