Optimisation suggestions for Min Heap

Question

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)

Answer 1

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".