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)
heapq
(or a wrapper around it) if it is faster? \$\endgroup\$please
girls (grey-haired to fully grown) thanoptimisations
, competence not withstanding.) \$\endgroup\$