# Optimisation suggestions for Min Heap

Can someone please optimisations for my implementation of min heap.Its performance is poor compared to the heapq module in python. My use case for the MinHeap class is 'N' insertions and extractions where N > 1,000,000.

import math

class MinHeap:
def __init__(self, arr):
self.__items = arr
self.build_heap()

def size(self):
"""
Returns the size of heap.
"""
return len(self.__items)

def items(self):
"""
Returns the elements in the heap.
"""
return self.__items

def build_heap(self):
"""
Builds heap using the list of elements.
"""
for node_number in xrange(int(len(self.__items) / 2), 0, -1):
self.heapify(node_number)

def heapify(self, node_number):
"""
Ensure that node follows heap property.
"""
# return if leave node
if node_number > int(len(self.__items) / 2):
return

node = self.__items[node_number-1]
left_child = self.__items[(2 * node_number)-1] if (((2 * node_number)-1) < len(self.__items)) else None

right_child = self.__items[(2 * node_number + 1)-1] if (((2 * node_number + 1)-1) < len(self.__items)) else None

min_node = node

if left_child != None and right_child != None:
min_node = min(node, left_child, right_child)
elif left_child != None :
min_node = min(node, left_child)
elif right_child != None :
min_node = min(node, right_child)

if min_node == node:
return
elif left_child!=None and min_node == left_child:

self.__items[node_number - 1], self.__items[(2 * node_number)-1] = self.__items[(2 * node_number)-1], self.__items[node_number - 1]
self.heapify(2 * node_number)
elif right_child!=None and min_node == right_child:

self.__items[node_number - 1], self.__items[(2 * node_number + 1)-1] = self.__items[(2 * node_number + 1)-1], self.__items[node_number - 1]
self.heapify(2 * node_number + 1)

def extract_min(self):
"""
Returns the minimum element.
"""
length = len(self.__items)
if length == 0:
return
self.__items[0], self.__items[length-1] = self.__items[length-1], self.__items[0]
min_element =  self.__items.pop()
self.heapify(1);
return min_element

def insert(self, num):
"""
Inserts a new element in the heap.
"""
self.__items.append(num)
current_node = len(self.__items)
parent_node = int(current_node / 2)
while current_node > 1:
min_node = min(self.__items[current_node-1], self.__items[parent_node-1])
if min_node == self.__items[parent_node-1]:
break
self.__items[current_node-1], self.__items[parent_node-1] = self.__items[parent_node-1], self.__items[current_node-1]
current_node = parent_node
parent_node = int(current_node / 2)

• Why don't you use heapq (or a wrapper around it) if it is faster? Feb 4, 2018 at 17:13
• @Graipher I think reinventing-the-wheel? Feb 4, 2018 at 17:50
• @hjpotter92 That's what I thought at first as well, but then they mentioned their use case explicitly, so I'm not so sure. Feb 4, 2018 at 18:36
• @Graipher I'm just trying to write the MinHeap class from scratch and optimise it to the point where its as efficient as 'heapq' Feb 5, 2018 at 6:00
• (I'd rather please girls (grey-haired to fully grown) than optimisations, competence not withstanding.) Feb 5, 2018 at 9:08

Docstrings with every method: Way to go, document MinHeap, too and revisit PEP257 for details.
Your MinHeap tackles the same task as module heapq using much the same strategy, and you express dissatisfaction with run time - a side by side comparison:

• in many places, you compute something like node_number or parent_node to repeatedly index __items - not using that variable, but something like parent_node - 1
(Code the way you think about it: if there are multiple places where you want the element at index i-1, write a[i-1], b[i-1]…, if you think same index happening to be i-1, write j = i-1, a[j], b[j]…)
(An optimising compiler can be expected to eliminate common sub-expressions; that is more difficult for an interpreter to justify (and I seem to remember why it might be hard for python).)
• insert() assigns the new value to every candidate position, while heapq._siftdown()/heappush() just moves down items of lesser priority and puts the new item once/twice.
• extract_min() swaps the items at both ends instead of just replacing the top priority item (see heapq.heappop())
• heapify() conditionally assigns None to left_child and right_child to go on and conditionally execute statements comparing these values to None (using != instead of is&not)
• heapq._siftup() uses the realistic approach of not comparing values "on the way down": half the nodes are leaf nodes, it is much more likely that the new item will end up near the bottom of the heap.
• heapq introduces heappushpop() as a "Fast version of a heappush followed by a heappop."

You seem to be bent on thinking of nodes numbered starting from 1 - nothing wrong with that, and coding the way you think about a solution/problem is the only sane way to start:
for a shot from the hip, allocate one more array element, don't use index 0 and drop all of "the - 1".