Heaps help you quickly retrieve objects with the smallest or the largest key.
From this definition, we can infer that we can use heaps to retrieve the maximum or minimum object in constant time.
Insertion
: Finding the exact position of the new element is performed in since it is only compared with the position of the parent nodes.Delete Min
: After the minimum element is removed, the heap has to put the new root in place.Find Min
: This is possible because the heap data structure always has the minimum element on the root node.Heapify
: This operation rearranges all the nodes after deletion or insertion operation. The cost of this operation is since all the elements have to be moved to keep the heap properties.Delete
: A specific element from the heap can be removed in time.Here’s a comparison between min heap vs. max heap.
"""Min Heap Implementation in Python"""class MinHeap:def __init__(self):"""On this implementation the heap list is initialized with a value"""self.heap_list = [0]self.current_size = 0def sift_up(self, i):"""Moves the value up in the tree to maintain the heap property."""# While the element is not the root or the left elementStop = Falsewhile (i // 2 > 0) and Stop == False:# If the element is less than its parent swap the elementsif self.heap_list[i] < self.heap_list[i // 2]:self.heap_list[i], self.heap_list[i // 2] = self.heap_list[i // 2], self.heap_list[i]else:Stop = True# Move the index to the parent to keep the propertiesi = i // 2def insert(self, k):"""Inserts a value into the heap"""# Append the element to the heapself.heap_list.append(k)# Increase the size of the heap.self.current_size += 1# Move the element to its position from bottom to the topself.sift_up(self.current_size)def sift_down(self, i):# if the current node has at least one childwhile (i * 2) <= self.current_size:# Get the index of the min child of the current nodemc = self.min_child(i)# Swap the values of the current element is greater than its min childif self.heap_list[i] > self.heap_list[mc]:self.heap_list[i], self.heap_list[mc] = self.heap_list[mc], self.heap_list[i]i = mcdef min_child(self, i):# If the current node has only one child, return the index of the unique childif (i * 2)+1 > self.current_size:return i * 2else:# Herein the current node has two children# Return the index of the min child according to their valuesif self.heap_list[i*2] < self.heap_list[(i*2)+1]:return i * 2else:return (i * 2) + 1def delete_min(self):# Equal to 1 since the heap list was initialized with a valueif len(self.heap_list) == 1:return 'Empty heap'# Get root of the heap (The min value of the heap)root = self.heap_list[1]# Move the last value of the heap to the rootself.heap_list[1] = self.heap_list[self.current_size]# Pop the last value since a copy was set on the root*self.heap_list, _ = self.heap_list# Decrease the size of the heapself.current_size -= 1# Move down the root (value at index 1) to keep the heap propertyself.sift_down(1)# Return the min value of the heapreturn root"""Driver program"""# Same tree as above example.my_heap = MinHeap()my_heap.insert(5)my_heap.insert(6)my_heap.insert(7)my_heap.insert(9)my_heap.insert(13)my_heap.insert(11)my_heap.insert(10)print(my_heap.delete_min()) # removing min node i.e 5
Free Resources