8
\$\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\$
  • 4
    \$\begingroup\$ You may be interested in heapq. \$\endgroup\$ – Peilonrayz Feb 22 '17 at 15:32
8
\$\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\$
  • \$\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\$ – oddcoder Mar 3 '17 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 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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