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

• You may be interested in heapq. – Peilonrayz Feb 22 '17 at 15:32
• 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. – netskink May 1 at 13:29

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]

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)

• 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 – oddcoder Mar 3 '17 at 12:43
• @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 – Peilonrayz Mar 3 '17 at 12:48

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

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