14
\$\begingroup\$

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)
\$\endgroup\$
2
  • 4
    \$\begingroup\$ You may be interested in heapq. \$\endgroup\$
    – Peilonrayz
    Feb 22, 2017 at 15:32
  • \$\begingroup\$ I like this implementation. I also like @peilonrayz answer below. FWIW, you can remove the operator import, compare parameter and implement a lt routine and it will be a min heap. Or, you can keep your compare and add each of the lt, gt, etc routines and specify which you desire via the compare parameter. Good job. \$\endgroup\$
    – netskink
    May 1, 2020 at 13:29

2 Answers 2

14
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ wouldn't it be better if the user was only allowed to pass the whole heap object to the constructor instead of the array list ? so it will be like this ? self.heap = [] if heap is None else heap.heap \$\endgroup\$
    – u185619
    Mar 3, 2017 at 12:43
  • 1
    \$\begingroup\$ @AhmedAbdElMawgood If you go that way you won't be able to pass normal arrays to it, IMO that's bad. With my way you would just have to passheap.heap. If you don't want that, but also want to be able to pass a normal list, then you may want to use: isinstance(heap, type(self)): heap = heap.heap, whilst keeping the option to take a normal array \$\endgroup\$
    – Peilonrayz
    Mar 3, 2017 at 12:48
2
\$\begingroup\$

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
\$\endgroup\$

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